online advertising

Friday, October 9, 2015

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 $

No comments:

Post a Comment