1
$\begingroup$

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?

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

3 Answers 3

2
$\begingroup$

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 !

enter image description here


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

$\endgroup$
1
  • 1
    $\begingroup$ Thanks, I will accept this solution over the others as it answers my question in a more general way. $\endgroup$
    – big-Oaf
    Commented Aug 18, 2023 at 19:07
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This clarifies so much! $\endgroup$
    – big-Oaf
    Commented Aug 18, 2023 at 19:07
0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – user16034
    Commented Aug 16, 2023 at 16:19
  • $\begingroup$ Yes, but thank you @Pseudonym for the additional insight. $\endgroup$
    – big-Oaf
    Commented Aug 18, 2023 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.