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

| cite | improve this answer | |
  • $\begingroup$ Thus no fixed $k$ will do for all $n$. I.e., $\log^k n$ is never in $\Omega(n^\alpha)$ for $\alpha > 0$. $\endgroup$ – vonbrand Feb 7 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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