Question

2. (10 Points) Fine an arrangement of the following functions fl, f2u10 so that fl-0(f2), f2 -O(f3),.., f(9)-0(f10). Also indicate which functions grow at the same asymptotic rate. lg[n!), In(n), n, 2(2n), 2(n*), nlg(n) lg(n), n2, 1, lg(n)

Answer 1

Sol: The required order of f1,f2,...,f10 is (Assuming log function is expressed for base 2)

1 , ln(n) , lg(n) , (lg(n))^2 , n , lg(n!) , nlg(n) , n^2 , 2^(n+1) , 2^(2n)

This order can be easily arrived at if we look at the graphs of all these functions and their rate of growth.

These following set of functions grow at the same rate:

-- ln(n) and lg(n)

-- 2^(n+1) and 2^(2n)