Performance of Quicksort

Worst-case partitioning:  What if each time the "divide" only separates itself from the rest:

         n                   n
        / \
          n-1                n-1
         /   \               
             n-2             n-2 
            /   \             .
                  .           .
                    .         .
                     1        1
                    /  \      ___
                              n^2

T (n) = T (n-1) + Q (n)

T (n) = Q ( n ² )

n å k = 0  k

= ( n ( n + 1 ) ) / 2 =  Q ( n 2 )

Worst-case is maximally unbalanced.

Best-case partitioning: each case divides in 2:

T (n) = 2 T ( n/2 ) +  Q (n)

Balanced partitioning:

T (n) = T ( 9 n / 10 ) + T ( n/10 ) + n

T (n) =  Q (n lg n)

Each step is about n, and ( 9/10 )ⁱ n = 1 Þ i = log_10/9 n steps.

Thus if you have a constant but very unbalanced break, you still get Q (n lg n)

Intuition for the balanced case: Partitioning depends on the value of the element chosen for the partition. If  it is the median each time that is best. But must expect that the element will produce good and bad splits. What if some of the splits are very bad and some are balanced. You still get Q ( lg n) levels so on the average you still have a cost of Q (n lg n). You only get a higher cost when almost all breaks are bad.