Sorting functions according to their Big-O complexity

user_14428208 0
Viewed 1100

Question: Sort the functions in increasing order of big-O complexity

  1. f1(n) = (n^0.999999) log n
  2. f2(n) = 10000000n
  3. f3(n) = 1.0000001^n
  4. f4(n) = n^2

My answer to this question is that is: 3, 2, 1, 4 (in increasing order) based on the rule that we can ignore constants.

But the answer I found in the solution booklet is:

The correct order of these functions is f1(n), f2(n), f4(n), f3(n).

I am not able to understand this. Can anyone explain? Here is the solution's explanation if it helps.

big-o time-complexity algorithm
1 Answers

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)).

user_69166310
Related