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

Running Time Analysis

The running time of the recursive sort method (Program gif) is given by

  equation37416

where n is the number of elements in sequence to be sorted, tex2html_wrap_inline68985 is the running time of the selectPivot method, and i is the number of elements which end up to the left of the pivot, tex2html_wrap_inline68989.

The running time of sort is affected by the selectPivot method in two ways: First, the value of the pivot chosen affects the sizes of the subsequences. That is, the pivot determines the value i in Equation gif. Second, the running time of the selectPivot method itself, tex2html_wrap_inline68985, must be taken into account. Fortunately, if tex2html_wrap_inline68995, we can ignore its running time because there is already an O(n) term in the expression.

In order to solve Equation gif, we assume that tex2html_wrap_inline68995 and then drop the tex2html_wrap_inline57196s from the recurrence to get

  equation37427

Clearly the solution depends on the value of i.