0
$\begingroup$

So I know that you can "prove" that $f(n) = O(g(n))$ by finding a constant $c$ such that $f(n) \le c \cdot g(n)$

This makes sense... but take a look at this.

Assume that

$$f(n) = n^{1.01}\\g(n) = n(\log(n))^2$$

Clearly here, $g(n) = n(\log(n))^2$ is the superior function.

But I was doing some tests and decided to swap the values and try to find a c for this inequality:

$$n^{1.01} \le c \cdot n(\log(n))^2$$

And if you plug in 5 for n, you get

$$5.08 \le 12.95c$$

Even if you made $c = 1$, it would definitely larger than $5.08$.

What does this mean? Is my understanding wrong? Or is it because just one is true, it doesn't necessarily mean the other can't also be?

$\endgroup$
3
  • $\begingroup$ What is wrong there? If $f(n) = O(g(n))$, it is very ok to get $f(5) \leq c \cdot g(5)$ for $c = 1$. $\endgroup$
    – Integral
    Oct 3, 2017 at 2:12
  • $\begingroup$ In fact, if you choose $c = 1$, then $f(n) \leq c \cdot g(n)$ for all $n \geq 2$. This proves that $f(n) = O(g(n))$. There is nothing strange here. $\endgroup$
    – Integral
    Oct 3, 2017 at 2:19
  • 1
    $\begingroup$ "Clearly here," Here is your mistake. It's not clear, and it's false. $\endgroup$
    – Clement C.
    Oct 3, 2017 at 13:38

2 Answers 2

0
$\begingroup$

Actually, you have that $f$ grows faster than $g$. The reason is that $n^.01$ grows faster than $(\ln(n))^2$. For example, let $n = e^{100000}$. Then $n^.01 = e^{1000} > 10^{400}$, but $(\ln(n)^2) = 100000^2 = 10^{10}.$

As it turns out, any positive power of $x$ grows faster than any power of $\ln(x)$. First, let's see that any positive power of $x$ grows faster than $\ln(x)$; just find the following limit using L'Hopital's rule: Let $a>0$. $$\lim_{x \to \infty} \frac{x^a}{\ln(x)} $$

For your problem, if you apply L'Hopital's rule twice to the following limit, you see that it equals $\infty$: $$\lim_{x \to \infty} \frac{x^.01}{(\ln x)^2}.$$ Or, you could just apply L'Hopital once to the following limit: $$\left(\lim_{x \to \infty} \frac{x^.01}{(\ln x)^2}\right)^.5 = \lim_{x \to \infty} \frac{x^{.005}}{\ln(x)}.$$

If the limit of a function is infinity, then raising the function to a positive power does not change the limit.


The meaning of $g(5) < f(5)$ is just that for small values of $n$, we have that $g$ is smaller than $f$. But this does not matter. Big Oh notation is about what happens for all LARGE values of $n$.

$\endgroup$
0
$\begingroup$

Clearly here, $g(n) = n(\log(n))^2$ is the superior function.

False. More generally, consider

$$f(n)=n^a \\ g(n)=n(\log n)^b$$

where $a>1$ and $b>0$.

So I know that you can "prove" that $f(n) = O(g(n))$ by finding a constant $c$ such that $f(n) \le c \cdot g(n)$

False. It has to hold true for all $n>N$, and we need to prove there is an $N>0$ such that this occurs.

Checking $n=5$ is not sufficient if $c=1$. In fact, if $c=1$, then you could pick

$$n>\exp\left[-\frac{b-1}{a-1}(-1-\sqrt{2x}-x)\right]$$

where

$$x=-1+\frac{b-2}{b-1}\ln(a-1)+\frac1{b-1}\ln(b)-\ln(b-1)$$

Whereupon you will find that

$$n^a>1\cdot n(\log n)^b$$

So,

$$n(\log n)^b\in\mathcal O(n^a)$$

That is, $n^a$ is the 'superior function'.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .