Consider the following simpler version of PARTITION for quic

Consider the following simpler version of PARTITION for quick sort: function simple PARTITION(i.j) x: = i + 1 y: = j while x lessthanorequalto y do if A[x] lessthanorequalto A[i] then x: = x + 1 else if A[y] > A[i] then y: = y - 1 else exchange A[x] and A[y] end Exchange A[i] and A[y]. return y - 1 and y + 1 end Prove that is correctly partitions. Prove that simple PARTITION can in the worst case use at most twice as many comparisons as PARTITION.

Solution

B. Let the number of comparisions in PARTITION be n with problem size n. In simplePARTITION the while loop is repeated until x<=y, ie the worst case can arise when the simplePARTITION divides the array such a way x is never <= y, in which case the problem size is reduced to n-1. Thus the recurrence relation will be:

T(n) = T(n-1) + n-1, if n>1

= 0 if n<=1

From this we get, T(n) = (n-1) + (n-2) + .........+2 + 1 = n(n-1) / 2

So the worst case complexity of simplePARTION is O(n ²) ie simplePARTITION is twice as many comparisions as PARTITION.