For instance, our example with four numbers had only two levels of recursion. A problem with eight
numbers will have three levels, and a problem with 16 numbers will have four.
Summing over the whole problem, then, we find the merge sort has a theta of n(lg n). There are (lg n) levels,
each with a theta of n. So the merge sort has an order of growth of ??(n(lg n)).
This is a very big deal, because for large sets of numbers, n(lg n) is very much smaller than n2. Suppose
that one million numbers must be sorted. The insertion sort will require on the order of (106)2, or
1,000,000,000,000 units of time, while the merge sort will require on the order of 106 (lg 106), or 106 (20),
or 20,000,000 units of time. The merge sort will be almost five orders of magnitude faster. If a unit of time is
one millionth of a second, the merge sort will complete in 20 seconds, and the insertion sort will require a week
and a half!
Binary search??”An example of order of growth of (lg n)??”Q(lg n)
Earlier we discussed the sequential search algorithm and found its performance to be ??(n). One can search
much more efficiently if one knows the list is in order to start with. The improvement in efficiency is akin to the
improved usefulness of a telephone book when the entries are sorted by alphabetical order.
Pages:
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67