Analysis of Quick Sort:

T(N) = T(i) + T(N - i -1) + cN

The time to sort the file is equal to

o the time to sort the left partition with i elements, plus

o the time to sort the right partition with N-i-1 elements, plus

o the time to build the partitions

1. Worst case analysis

The pivot is the smallest element

T(N) = T(N-1) + cN, N > 1

Telescoping:

T(N-1) = T(N-2) + c(N-1)

T(N-2) = T(N-3) + c(N-2)

T(N-3) = T(N-4) + c(N-3)

T(2) = T(1) + c.2

Add all equations:

T(N) + T(N-1) + T(N-2) + … + T(2) =

= T(N-1) + T(N-2) + … + T(2) + T(1) + c(N) + c(N-1) + c(N-2) + … + c.2

T(N) = T(1) + c(2 + 3 + … + N)

T(N) = 1 + c(N(N+1)/2 -1)

Therefore T(N) = O(N2)

1. Best-case analysis:

The pivot is in the middle

T(N) = 2T(N/2) + cN

Divide by N:

T(N) / N = T(N/2) / (N/2) + c

Telescoping:

T(N/2) / (N/2) = T(N/4) / (N/4) + c

T(N/4) / (N/4) = T(N/8) / (N/8) + c

……

T(2) / 2 = T(1) / (1) + c

Add all equations:

T(N) / N + T(N/2) / (N/2) + T(N/4) / (N/4) + …. + T(2) / 2 =

= (N/2) / (N/2) + T(N/4) / (N/4) + … + T(1) / (1) + c.logN

After crossing the equal terms:

T(N)/N = T(1) + cLogN = 1 + cLogN

T(N) = N + NcLogN

Therefore T(N) = O(NlogN)

1. Average case analysis

Similar computations, resulting in T(N) = O(NlogN)

The average value of T(i) is 1/N times the sum of T(0) through T(N-1)

1/N  T(j), j = 0 thru N-1

T(N) = 2/N ( T(j)) + cN

Multiply by N

NT(N) = 2( T(j)) + cN*N

To remove the summation, we rewrite the equation for N-1:

(N-1)T(N-1) = 2( T(j)) + c(N-1)2, j = 0 thru N-2

and subtract:

NT(N) - (N-1)T(N-1) = 2T(N-1) + 2cN -c

Prepare for telescoping. Rearrange terms, drop the insignificant c:

NT(N) = (N+1)T(N-1) + 2cN

Divide by N(N+1):

T(N)/(N+1) = T(N-1)/N + 2c/(N+1)

Telescope:

T(N)/(N+1) = T(N-1)/N + 2c/(N+1)

T(N-1)/(N) = T(N-2)/(N-1)+ 2c/(N)

T(N-2)/(N-1) = T(N-3)/(N-2) + 2c/(N-1)

….

T(2)/3 = T(1)/2 + 2c /3

Add the equations and cross equal terms:

T(N)/(N+1) = T(1)/2 +2c  (1/j), j = 3 to N+1

T(N) = (N+1)(1/2 + 2c (1/j))

The sum  (1/j), j =3 to N-1, is about LogN

Thus T(N) = O(NlogN)

We have set a pivot for the given numbers by which we can apply quick sort algorithm.

Hence after applying the quick sort technique the sorted numbers are

0, 1, 3, 5, 9, 7, 12