Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Worst-Case Running Time

In the worst case the i in Equation gif is always zero.gif In this case, we solve the recurrence using repeated substitution like this:

eqnarray37606

The worst case occurs when the two subsequences are as unbalanced as they can be--one sequence has all the remaining elements and the other has none.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.