Algorithms: Design and Analysis, Part 1 - Problem Set 1 - Question 5

Problem:

Arrange the following functions in increasing order of growth rate (with g(n) following f(n) in your list if and only if f(n)=O(g(n))).

a) $\sqrt{n}$
b) $10^n$
c) $n^{1.5}$
d) $2^{\sqrt{\log n}}$
e) $n^{\frac{5}{3}}$

Solution:

The simplest approach I can think of is to compute a bunch of values:

	$\sqrt{n}$	$10^n$	$n^{1.5}$	$2^{\sqrt{\log n}}$	$n^{\frac{5}{3}}$
1	1	10	1	1	1
2	1.4142	100	2.8284	1.4627	3.1748
3	1.7321	1000	5.1962	1.6141	6.2403
4	2	10000	8	1.7123	10.079
5	2.2361	100000	11.18	1.7851	14.62
6	2.4495	1E+06	14.697	1.8431	19.812
7	2.6458	1E+07	18.52	1.8912	25.615
8	2.8284	1E+08	22.627	1.9323	32
9	3	1E+09	27	1.9682	38.941
10	3.1623	1E+10	31.623	2	46.416
11	3.3166	1E+11	36.483	2.0286	54.407
12	3.4641	1E+12	41.569	2.0546	62.898
13	3.6056	1E+13	46.872	2.0783	71.874
14	3.7417	1E+14	52.383	2.1003	81.323
15	3.873	1E+15	58.095	2.1206	91.233
16	4	1E+16	64	2.1396	101.59
17	4.1231	1E+17	70.093	2.1573	112.4
18	4.2426	1E+18	76.368	2.1741	123.63
19	4.3589	1E+19	82.819	2.1898	135.29
20	4.4721	1E+20	89.443	2.2048	147.36

Now it is totally obvious the order should be

$2^{\sqrt{\log n}} < \sqrt{n} < n^{1.5} < n^{\frac{5}{3}} < 10^n$

In fact, looking it in retrospective, after taking log (and remember in asymptotics base does not matter), the solution is very obvious.

In the sublinear range, we have $\sqrt{\log n} < \frac{1}{2}\log{n}$ 

In the polynomial range, we have $1.5 < \frac{5}{3}$

Exponential grow fastest $10^n$