2
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • $\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, 2020 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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