Discrete Mathematics for Computer Science

388 CHAPTER 6 Graph Theory

a

bC

a.-b

C cb~

b:c a b:c

a<b a< b b<a c <a

b<c ,<c ~ ",,<,

a~c°/b a/•b: cb

[ -•bf - a < b a < b -a- b < < -•ai

c<b Ca<c c<b c<a /\c<a

c<a bc cb

Figure 6.52 Decision tree for sorting three elements.

The number of vertices with boxes must be at least n!, since there are that many

possible orderings of n elements. Obviously, a sorting algorithm must be able to identify

each of these orderings.

The level of any vertex turns out to be the number of comparisons that must be made to

get from the starting question to the vertex-that is, the number of edges traversed in going

from the root of the tree to the vertex. Since each comparison results in one of two possible

answers, after k comparisons at most 2 k different vertices can be labeled with orderings.

Let S(n) be the minimum number of comparisons used by any sorting algorithm that

correctly sorts any input of n elements. The decision tree representing any sorting-by-

comparisons algorithm must have at least S(n) levels.

Thus, the decision tree representing any sorting-by-comparisons algorithm must have

at least S(n) levels. Since at most 2 S(n) orderings can be represented by vertices in a tree

with S(n) levels, we must have

2 S(n) > n!

S(n) >: 1092(n!)

The problem is to find a good approximation for log 2 (n!).

Example 2. O(log 2 (n!)) = O(n log(n)).

Solution. We must prove that (a) log(n!) E O(n log(n)) and (b) n log(n) e O(log(n!)).

(a)

log 2 (n!) = log 2 (1) + 1092(2) + 1og 2 (3) +-.- + log 2 (n - 1) + log 2 (n)

< log 2 (n) + log 2 (n) + log 2 (n) +.. + log 2 (n) + log 2 (n)

= n log 2 (n)

Now, let c = 1 and No = 1. Since n log 2 (n) < c log 2 (n!) for all n > No, we conclude that

log 2 (n!) E O(n log 2 (n)).