sorting functions according to their big-o complexity

The following facts reveal the ordering:

1. O(n^k) > O(log(n)) for any k > 0.
2. O(k^n) > O(n^b) for any k > 1.

This might feel counter-intuitive since 1.0000001^n starts off really slow, but we are talking of asymptotic complexity here. The exponential growth, albeit slow in practical scenarios, dominates any polynomial growth as we go towards infinity. And the same is true for polynomial growth being greater than logarithmic growth.

So:

• f3(n), with the exponential growth is of highest complexity.
• f4(n) being greater than f2(n) and f1(n) is quite obvious.
• f1(n) vs f2(n) — Consider them n^0.999999 * logn vs n^0.999999 * n^0.000001. So what determines the comparison here is logn vs n^0.000001. As we have stated in fact (1), polynomial growth > logarithmic growth. So f2(n) > f1(n).

Combining the results, we have O(f1(n)) < O(f2(n)) < O(f4(n)) < O(f3(n)).