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

Question

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.

Answer 1

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