This can be written
as log2 n, but in computer science, because of the ubiquity of binary math, this is usually written as lg n, meaning
logarithm to the base 2 of n.
The total running time T of the merge sort consists of the time to recursively solve two problems of half
the size, and then to combine the results. One way of expressing the time required is this:
T = 2T(n/2) + merge
Since merge runs in ??(nA + nB), and since nA + nB = n, we will restate this:
T = 2T(n/2) + ??(n)
A recursion tree is a way to visualize the time required. At the top level, we have the time required for
merge ??(n), plus the time required for the two subproblems:
??(n)
T(n/2) T(n/2)
At the next level, we have the time required for the two merges of the two subproblems, and for the further
subdivision of the two subproblems:
??(n)
??(n/2) ??(n/2)
T(n/4) T(n/4) T(n/4) T(n/4)
CHAP. 2] ALGORITHMS 21
We can continue this sort of expansion until the tree is deep enough for the size of the overall problem:
??(n)
??(n/2) ??(n/2)
??(n/4) ??(n/4) ??(n/4) ??(n/4)
...
...
Adding across each row, we find:
Sum
??(n) ??(n)
??(n/2) ??(n/2) ??(n)
??(n/4) ??(n/4) ??(n/4) ??(n/4) ??(n)
...
...
For any particular problem, because we repetitively divide the problem in two, we will have as many levels
as (lg n).
Pages:
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66