CODEWITHSUNDEEP
mathtime-complexitycomplexity-theory
zangsy
zangsy

Reputation: 35

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

Upvotes: 1

Views: 2238

Answers (1)

One Lyner
One Lyner

Reputation: 2004

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!

Upvotes: 1

Related Questions