What's a better time complexity, $O(\log^2(n))$, or $O(n)$?

Question

(By $O(\log^2(n))$, I mean $O((\log n)^2)$ rather than $O(\log(\log(n)) )$

I know $O(\log(n))$ is better than $O(\log^2(n))$ which itself is better than $O(\log^3(n))$ etc. But how do these compare to $O(n)$? Is there a certain point where when you keep tacking on these logs, they surpass linear time complexity? When does this happen?

Answer 1

We know that $\log{n} \lt n$ [[ I will leave out $O(\cdot)$ to keep it readable & easy to type ]]

We want to know whether there is some $P$ where $\log^{P}{n} \lt n \lt \log^{P+1}{n}$ that makes the Polylogarithm larger than linear.

Take $log(\cdot)$ here :
$\log{\log^{P}{n}} \lt \log{n} \lt \log{\log^{P+1}{n}}$
$P\log{\log{n}} \lt \log{n} \lt (P+1)\log{\log{n}}$
$P\log{\log{n}}/\log{n} \lt 1 \lt (P+1)\log{\log{n}}/\log{n}$

We know that $\log{\log{n}}/\log{n} \rightarrow 0$ when $n \rightarrow \infty$ , hence this is :
$P \times 0 \lt 1 \lt (P+1) \times 0$
$0 \lt 1 \lt 0$
Contradiction ! Hence there is no such $P$ to make Polylogarithm linear.