0

I have a feeling $f$ grows faster than $g$, and therefore it is not the case that $f \in O(g)$, but no matter how much I try, I do not see how to prove it.

Any help?

Nate Eldredge
  • 97,710
Flavio Tisi
  • 11

2 Answers2

1

I am assuming all logarithms are in base $2$, but the conclusion wouldn't change if the $\log$ was the natural one.

So, you have $$ f(n) = 5^{\log(n)^2} = 2^{\log(5)\cdot\log(n)^2} $$ while $$ g(n) = n^{\log(n)} = 2^{\log(n)\cdot\log(n)} = 2^{\log(n)^2} $$

Therefore, $$ \frac{f(n)}{g(n)} = 2^{\log(5)\cdot\log(n)^2 - \log(n)^2} = 2^{(\log 5 - 1)\log(n)^2} \xrightarrow[n\to\infty]{} \infty $$ since $\log 5 -1 > 0$. Can you conclude?

Clement C.
  • 67,323
  • 1
    But the bases do matter though. If you were taking base 4 (say) i.e., $\log n \doteq \log_4 n$, then $n^{\log n} = 2^{2 \log n \cdot \log n}$ and not $2^{\log n \cdot \log n}$ as you wrote above. – Mike Feb 15 '19 at 00:46
  • Yes (as the last line says, it relies on $\log 5 > 1$). When I said "the conclusion wouldn't change", it's because I assumed the base would be either $2$ (binary, standard for these computer-science-type exercises) or $e$ (natural). Nobody would consider $\log_{17}$ and just write it $\log$ (base 10 in the option, of course, but it seems highly unlikely to me, again). @Mike – Clement C. Feb 15 '19 at 00:49
  • Indeed no one takes base 17 but working base 10 is definitely not unheard of even in CS. I could see someone reading what you wrote and assuming that it would hold if we were working base 10 – Mike Feb 15 '19 at 00:54
  • 1
    @Mike Fair, I edited the first sentence to mention base 2 or base $e$. – Clement C. Feb 15 '19 at 00:55
  • Yes, I think now I can conclude. Thank you! – Flavio Tisi Feb 15 '19 at 08:40
  • You're welcome! – Clement C. Feb 15 '19 at 15:00
0

The base that you take the logs do matter. For example on the one hand let's assume that the base is much bigger than 5; e.g, for example $\log n \doteq \log_{125} n$:

$$5^{\log^2_{125} n} = (5^{\log_{125} n})^{\log_{125} n} = (n^{\frac{1}{3}})^{\log_{125} n} = (n^{\log_{125} n})^{\frac{1}{3}} = g^{\frac{1}{3}}.$$

On the other hand let us now assume that the base is $2<5$ e.g, for example $\log n \doteq \log_{2} n$:

$$5^{\log^2_2 n} > 4^{\log^2_2 n} = (4^{\log_2 n})^{\log_2 n} = (n^2)^{\log_2 n} = (n^{\log_2 n})^2 = g^2.$$

So can you conclude for yourself the following: Iff the base is 5 or greater (e.g., 10) then $f \in O(g)$. If the base is less than 5 (i.e., 2 or $e$) then $f \not \in O(g)$.

Mike
  • 20,434