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

Best-Case and Worst-Case Running Times

In Section gif we derived the average running time of Program gif which finds the largest element of an array. In order to do this we had to determine the probability that a certain program statement is executed. To do this, we made an assumption about the average input to the program.

The analysis can be significantly simplified if we simply wish to determine the worst case running time. For Program gif, the worst-case scenario occurs when line 8 is executed in every iteration of the loop. We saw that this corresponds to the case in which the input array is ordered from smallest to largest. In terms of Equation gif, this occurs when tex2html_wrap_inline57382. Thus, the worst-case running time is given by

eqnarray824

Similarly, the best-case running time occurs when line 8 is never executed. This corresponds to the case in which the input array is ordered from largest to smallest. This occurs when tex2html_wrap_inline57384 and best-case running time is

eqnarray833

In summary we have the following results for the running time of Program gif:

gather840


next up previous contents index

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