-
O(1) < O(log(n)) < O(n^1/2) < O(n) < O(n.log(n)) < O(n^2) < O(2^n) < O(n!)
-
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.