The big-O hierarchy: A few basic facts about the big-O behaviour of some familiar functions are very important. Let p(n) be a polynomial in n (of any degree). Then
log_{b}n is O(p(n)) and p(n) is O(a^{n});
for any base b and any a. In words: logs are big-O of polynomials and polynomials are big-O of exponentials.
Note that since log_{b}n = log_{c}n/ log_{c}b, we have
log_{b}n is O(log_{c}n);
for any fixed b and c, since log_{c}b is a constant.