0
$\begingroup$

Had this question on an algorithm exam. Can any one explain why $\sqrt{n} = \Omega(3^{\log n})$ is false?

$\endgroup$
1
  • 2
    $\begingroup$ It really depends on the base of the logarithm. $\endgroup$ – Yuval Filmus Nov 14 '17 at 22:44
5
$\begingroup$

We'll start with some arithmetic, and assume the base of the logarithm to be $x$. First, remember the log law: $$ \log_{a}(b) = \frac{\log_{c}(b)}{\log_{c}(a)} $$ So $$ \begin{array}{rl} 3^{\log_{x}(n)} &= 3^{\frac{\log_{3}(n)}{\log_{3}(x)}}\\ &=(3^{\log_{3}(n)})^{1/\log_{3}(x)} &=n^{1/\log_{3}(x)} \end{array} $$ Whether $n^{\frac{1}{2}}$ is in big-omega of this then depends on what $x$ is.

If we make the right and proper computer science assumption that the base 2 logarithm is the only logarithm (that was a joke of course), then $1/\log_{3}(x)=1/\log_{3}(2)\approx 1.6$, which is certainly bigger than $1/2$.

You'd need $x\geq 9$ for the statement to be true.

$\endgroup$
1
  • $\begingroup$ The problem actually states log base is 2. I forgot to add it. Thank you $\endgroup$ – klijia Nov 14 '17 at 23:27

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