# Values of k that make this true, $\log^k n \in \Omega(\sqrt n)$

I have seen some algorithms with complexities like $$\log^3 n$$ and $$\sqrt n$$. In view of getting a better idea on how to compare these I wanted to know for which values of $$k$$ does $$\log^k n \in \Omega(\sqrt n)$$ hold true?

I suspect $$k$$ would need to be a function of $$n$$. Because if it were a constant $$C_1$$, we could always find a larger constant $$C_2$$ that makes the previous statement false.

This is what I have tried.

$$\log^k n \in \Omega(\sqrt n)$$

$$\log^{2k} n \in \Omega(n)$$

$$\log(\log^{2k}n) \in \Omega(\log n)$$

$$2k \log\log n \in \Omega(\log n)$$

From here, I can see that if $$k$$ is $$\log n$$, then $$2\log n \log\log n \in \Omega(\log n)$$ is true.

However, I doubt this is a tight bound.

Let's redo your calculation. You want $$\log^kn \geq C \sqrt{n}$$ to hold for some $$C>0$$ and large $$n$$. Taking the logarithm, $$k \log \log n \geq \log C + \tfrac{1}{2}\log n,$$ and so $$k \geq \frac{\log C + \tfrac{1}{2}\log n}{\log\log n}$$ should hold for large $$n$$. In other words, $$k = \frac{\log n}{2\log\log n} + \Omega\left(\frac{1}{\log\log n}\right).$$
• Thus no fixed $k$ will do for all $n$. I.e., $\log^k n$ is never in $\Omega(n^\alpha)$ for $\alpha > 0$. – vonbrand Feb 7 at 22:51