Cormen 1.2.2

Cormen_122.jl

# for n = 1, `log(2, 1) = 0`, making merge time equal 0
# start with n = 2

julia> n = 2;

julia> insertiontime = 8*n^2;

julia> mergetime = 64*n*log(2,n);

julia> while true 
            println(n)
            if insertiontime > mergetime 
                break
            end
            n += 1 
            insertiontime = 8*n^2 
            mergetime = 64*n*log(2,n) 
            println(insertiontime)
            println(mergetime)
       end
2
72 # insertion time
304.31280013846197 # merge time
3
128
512.0
4
200
743.0169903639559
5
288
992.6256002769239
6
392
1257.6950050818066
7
512
1536.0
8
648
1825.876800830772
9
800
2126.033980727912
10
968
2435.4398595206576
11
1152
2753.2512005538483
12
1352
3078.7658454933885
13
1568
3411.3900101636127
14
1800
3750.614971784178
15
2048
4096.0
16
2312
4447.15957128037
17
2592
4803.753601661543
18
2888
5165.4798563474
19
3200
5532.067961455824
20
3528
5903.274616214654
21
3872
6278.879719041314
22
4232
6658.683199315923
23
4608
7042.502401107697
24
5000
7430.169903639559
25
5408
7821.531690986778
26
5832
8216.445603738475
27
6272
8614.780020327225
28
6728
9016.412726956774
29
7200
9421.229943568356
30
7688
9829.125479807562
31
8192
10240.0
32
8712
10653.760380085054
33
9248
11070.31914256074
34
9800
11489.593957956724
35
10368
11911.507203323086
36
10952
12335.985569809354
37
11552
12762.9597126948
38
12168
13192.363938280172
39
12800
13624.135922911648
40
13448
14058.216460117852
41
14112
14494.549232429308
42
14792 # insertion time is still smaller than
14933.080604940173 # merge time
43 
15488 # insertion time is greater than
15373.759438082629 # merge time
44 # loop breaks. for 2 < n < 43, insertion time < merge time

julia>