Question

What is the worst – case performance of Quicksort? Prove it.

Answer 1

Worst case performance of Quicksort is when it divides the array into sizes 1 and n-1

Then
Recurrence relation for the Quicksort function is
T(n) = T(n-1) + n

Solving Recurrence relation 
T(n) = T(n-1) + n
     = T(n-2) + (n-1) + n
     = T(n-3) + (n-2) + (n-1) + n
     = T(n-4) + (n-3) + (n-2) + (n-1) + n
     ....
     ....
     = T(n-n) + 1 + ... + (n-3) + (n-2) + (n-1) + n
     = T(0) + 1 + ... + (n-3) + (n-2) + (n-1) + n
     = 0 + 1 + ... + (n-3) + (n-2) + (n-1) + n
     = 1 + ... + (n-3) + (n-2) + (n-1) + n
     = n(n+1)/2
    = (n^2+n)/2
    = O(n^2)