CODEWITHSUNDEEP
time-complexitybig-o
sadfs
sadfs

Reputation: 13

which one is better? O(n^1/2) or O(logn)

Can anyone explain to me which one is better: O(n^1/2) or O(logn). The complexity table in text book says O(logn) is better than O(n) and O(n^2). I think I can conclude that O(logn) is better than O(n^k) where k>=1, but how about when k is between 0 and 1. Is O(logN) still better? Thank you

Upvotes: 1

Views: 8225

Answers (1)

Onur Gumus
Onur Gumus

Reputation: 1439

While n goes to infinity logn is strictly smaller than n^k where 0 < k < 1. (It can be proved by L'Hopitals rule from calculus I guess.) Thus O(logn) is preferable.

Upvotes: 5

Related Questions