Time Complexity of Quick Sort

sort(int a[], int lb, int ub){

if (lb >= ub) return;

j = partition(a,lb,ub); /* O(n) */

sort(a,lb,j-1);

sort(a,j+1,ub);

}

Worst case:

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

O(n2)

Best case:

T(n)=n+2*t(n/2)

O(nlogn)