Analysis of Algorithms : An Active Learning Approach

50 SEARCHING AND SELECTION ALGORITHMS

means that we can determine the total number of comparisons done for every

possible case by adding, for every level, the product of the number of nodes on

each level and the number of comparisons for that level. This gives an average

case of analysis of

We can use Equation 1.19 to simplify this equation to

BecauseN = 2k
 1, 2k = N + 1.

AsN gets larger, k/N becomes zero, giving

AN() N----^1 i 2 i–1 forN

i=1

k

∑^2

==k– 1

AN() N----^1 *^12 -- i 2 i

i=1

k

= ∑

AN()= N----^1 *^12 -- * []()k– 1 2 k+1+ 2

AN()= N----^1 []()k– 1 2 k+ 1

AN()= N----^1 []k 2 k– 2 k+ 1

AN() k^2

[]k–() 2 k– 1

N

= ---------------------------------------

AN() k^2

[]k–N

N

= -------------------------

AN() k^2

k

= ---------N-– 1

AN() kN()+^1

N

= ---------------------– 1

AN()

kNk* +

= ----------------------N – 1

AN()≈k– 1

AN()≈lg()N+ 1 – 1

forN = 2 k– 1

forN = 2 k– 1