Search code examples
mathtime-complexitycomplexity-theory

Is time comlexity O((log(N))^2) equivalent to O(sqrt(N))?


I saw the following equivalence in the lowest common ancestor problem:
1
but I don't understand why, so I want to figure out how to prove:
enter image description here


Solution

  • As explained by @Joni, you can prove that log(N)^2 < 16 * sqrt(N), which gives the expected big-O notation.

    But you might be troubled because this equal sign is a "one way" one:

    O(log(N)^2) = O(sqrt(N)) is true, but O(sqrt(N)) = O(log(N)^2) is false!