CSC 378: Data Structures and Algorithm Analysis

ANALYSIS OF RECURSIVE PROGRAMS

The Iterative Method

[CLR 4.2]

Here's an example in which we analyze MergeSort.

Given a list index1.gif of length index2.gif , what is MergeSort's running time, index3.gif ?

Here's the analysis of the individual parts of MergeSort:

index4.gif first half of index5.gif index6.gif
index7.gif second half of index8.gif index9.gif
MergeSort( index10.gif ) index11.gif
MergeSort( index12.gif ) index13.gif
Merge( index14.gif , index15.gif ) index16.gif

And here's how we fit it all together:

index17.gif

Therefore, index18.gif .

How Much recursion?

Recursion stops when index19.gif . How much recursion occurs? In the example above, we had the sequence:

index20.gif

The argument of index21.gif was

index22.gif

Q: Recursion stops when index23.gif . When does this happen?

A: When

index24.gif

So recursion stops after index25.gif levels.

Another Iterative Example

[CLR 4.2]

index26.gif

Also see "Recursion Trees" in [CLR 4.2].




Back to the lecture index

Copyright 1998     James Stewart