How do these pairs of functions compare asymptotically:
- $$n^{17}$$ and $$2^n$$
- $$2^{n^2}$$ and $$10^n$$
Difficulty level
This exercise is mostly suitable for students
We would like to evaluate lim f(n)/g(n) as n tends to infinity. One very helpful tool in evaluating limits is L’Hopital’s rule, which states that assuming certain conditions apply, lim n->infinity f(n)/g(n) = lim n->infinity f’(n)/g’(n) , where f’(n) and g’(n) represent the first derivatives of functions f(n) and g(n) respectively.
Applying this to our case, we obtain that:
f’(n) = 17 n^16 and g’(n) = 2^n ln (2) .
We can repeat this process a few more times (16 to be precise!), and at that point, we have that:
lim n-> infinity 17! /(2^n(ln 2)^17 ) which is obviously 0 .
Since lim n->infinity n^17 / 2^n = 0 , we conclude that n^17 = o( 2^n ) .
These two functions appear to be difficult to compare, since 2 < 10 , and n^2 > n. So, which effect dominates? One way is to simply try a large value of n , such as 100 to obtain a clue. 2^{10000} appears to be much larger than 10^{100} , especially if we consider that 2^{400} is already larger than 10^100 (since 2^4 > 10 ). So, the clue is quite clear that 2^{n^2} is larger than 10^n , but how do we prove the asymptotic omega relationship? Once again, we use the limit method.
lim n->infinity 10^n /2^n^2 = lim n->infinity 10^n /2^nn
​ = lim n->infinity (10/2^n)^n
​ = 0
Therefore, we conclude that 10^n = o(2^{n^2} ) Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Sorting using the counting sort algorithm