$\sqrt{n} = \Omega(3^{\log{}n})$ is not true? Why? [duplicate]

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

• It really depends on the base of the logarithm. Nov 14 '17 at 22:44

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.