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:
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