Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
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:

eqnarray37355

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 © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.