Analysis of Algorithms : An Active Learning Approach

30 ANALYSIS BASICS

leaf represents the worst case. The best case is the shortest path. The average

case is the total number of edges in the decision tree divided by the number of

leaves in the tree. As simple as it would seem to be able to determine these

numbers by drawing decision trees and counting, think about what the deci-

sion tree would look like for a sort of 10 numbers. As was said before, there

are 3,628,800 different ways these can be ordered. A decision tree would need

at least 3,628,800 different leaves, because there may be more than one way to

get to the same order. This tree would then need at least 22 levels.

So, how can decision trees be used to give us an idea of the bounds on an

algorithm? We know that a correct sorting algorithm must properly order all

of the elements no matter what order in which they begin. There must be at

least one leaf for every possible permutation of input values, which means that

there must be at least N! leaves in the decision tree. A truly efficient algorithm

would have each permutation appear only once. How many levels does a tree

withN! leaves have? We have already seen that each new level of the tree will

have twice as many nodes as the previous level. Because there are 2K–1 nodes

on level K, our decision tree will have L levels, where L is the smallest integer

withN!≤ 2 L–1. Applying algebraic transformations to this formula we get

Because we are trying to find out the smallest value for L, is there anyway to

simplify this equation further to get rid of the factorial? Let’s see what we can

observe about the factorial of a number. Consider the following:

By Equation 1.5, we get

By Equation 1.21, we get

lgN!≤L– 1

lgN!lg= ()N ()N– (^1) ()N– (^2) ... 1
lg()N ()N– (^1) ()N– (^2) ... 1 = lg()N ++++lg()N– 1 lg()...N– 2 lg(1)
lg()N ++++lg()N– 1 lg()...N– 2 lg 1() lgi
i=1
N
= ∑
lgi
i=1
N
∑ ≈N lg N–1.5
lgN!≈N lg N