Position of Pivot Left of pivot Right of pivot T(n left ) T(n right ) 1 0 n-1 T(0) T(n-1) 2 1 n-2 T(1) T(n-2) 3 2 n-2 T(2) T(n-3) --- --- --- --- -- --- --- --- --- --- --- --- --- --- --- n-2 n-3 2 T(n-3) T(2) n-1 n-2 1 T(n-1) T(1) n n-1 0 T(n-1) T(0) The number of comparisons for first call on partion: Assume left_to_right moves over k smaller element and thus k comparisons. So when right_to_left crosses left_to_right it has made n-k+1 comparisons. So first call on partition makes n+1 comparisons. The average case complexity of quicksort is: {T(n) = comparisons for first call on quicksort + Σ 1 [T(n left )+T(n right )]} =(n+1) + 2[T(0) + T(1) + T(2) + ----T(n-1)/n.....(1) So, nT(n) = n(n+1) + 2[T(0) + T(1) + T(2) + --- +T(n-2) + T(n-1)] .......(2) (n-1)T(n-1) = (n-1)n + 2[T(0) ...