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

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?

• Btw, also $n^{1.03} = \Omega(n\log(n))$ holds. Aug 15 at 14:56

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))).$$

• Thanks, I will accept this solution over the others as it answers my question in a more general way.
– pod
Aug 18 at 19:07

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.

• This clarifies so much!
– pod
Aug 18 at 19:07

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.

• I don't think that this answers the question. $\log_{10}(\log_{10}(n))$ and $\log_{2}(\log_{2}(n))$ differ by a linear relation. This is probably what the OP wants to understand.
– user16034
Aug 16 at 16:19
• Yes, but thank you @Pseudonym for the additional insight.
– pod
Aug 18 at 19:05