Is $n^{1.03} = \Omega(n \log \log n)$?

Question

We had this problem on our Algorithms final. It threw me off because if $\log$ is $\log_2$ then graphing the function shows this is not true, but if $\log$ is $\log_{10}$ then it looks like it is. How can this idea be formalised?

Answer 1

To compare complexity orders, plots are your false friends. Because you may need to look at astronomical values to detect curve crossings. Nothing replaces analytical study.

For example, on a plot $n^{30}$ (in blue) seems to completely outperform $3^n$, but in reality, the latter grows much faster !

---

You are probably aware that $e^x=\Omega(x)$ [by Taylor, $e^x>1+x+\frac{x^2}2$]. This implies $e^{ax}=\Omega(ax)=\Omega(x)$, for any $a>0$. Now we can replace $x$ by $\log(n)$ and get

$$n^a=\Omega(\log(n))$$ and $$n^{a+1}=\Omega(n\log(n)).$$

Needless to say, this implies

$$n^{a+1}=\Omega(n\log(\log(n))).$$

Answer 2

Remove a factor n, then the question is whether $n^{0.03} = O(\log \log n)$. The problem is that $n^{0.03}$ grows very fast, but not for small n, not for large n, but for absolutely huge n.

Assume "log" is the base 2 logarithm. Then for $n = 2^{100}$ we have $n^{0.03} = 2^{100 \cdot 0.03} = 2^3 = 8.$ $\log \log n$ on the other hand is $\log \log 2^{100} = \log 100 \approx 6.9$. Almost the same. If you draw a graph up to the huge $n = 2^{100}$ it looks quite plausible that the answer to your question is yes. Take $n = 2^{1000}$ and now you are comparing $2^{30}$ to $\log 1000 \approx 10$. Take $n = 2^{10000}$ and now you are comparing $2^{300}$ to $\log 10000 \approx 13.1$. $n^{0.03}$ grows faster than the logarithm and the logarithm of the logarithm.

Answer 3

Recall what big-omega means.

$f(n)$ is $\Omega(g(n))$ if there exists an $n_0$ and a constant $c$ such that for all $n > n_0$, $f(n) \ge c\cdot g(n)$.

To satisfy this definition, $n_0$ can be as large as it needs to be, and $c$ can be as small as it needs to be. Part of the challenge is finding a suitable $n_0$ and $c$.

As a hint, to get you started:

$$\log_2 x = \frac{1}{\log_{10} 2}\log_{10} x$$

That is, $\log_2 x$ is $\log_{10} x$ up to a constant factor. This is part of why, in asymptotic analysis, we can often just say $\log n$ without specifying the base.