Question

Write a decrease-conquer algorithm to solve the following problem:

input: a nonempty unsorted array A[lo..hi] of n distinct nonnegative integers;

output: the (left) median value of A[lo..hi].

What is the asymptotic running time of your algorithm ?

Answer 1

Let the algorithm be known as decrease-conquer(A,lo,hi) which takes three inputs one is array , lo is its lower index as given and hi is higher index as given. median is nothing but (n/2)^th smallest element in sorted array.

let hi - lo + 1 = n.

C style psuedoCode:-

decrease-conquer(A,lo,hi)//suppose it takes T(n)

{

if(lo==hi)// it takes c1 time

return A[lo]// it takes c2 time

else

{

m = partition(A,lo,hi) // it takes O(n) time

if(m = (hi-lo + 1) / 2) // // it takes c3 time

return A[m]

else

if(m>(hi-lo + 1) / 2)// it takes c4 time

decrease-conquer(A,lo,m-1)// it takes T(m-lo) time

else

decrease-conquer(A,m+1,hi)// it takes T(hi-m) time

}

}

partition(A,lo,hi)

{

x = A[lo]//pivot

i = lo

j = i+1

while(j<=hi)//as long as j is smaller or equal to hi

{

if(A[j] <= x)

{

i++

swap(A[i] , A[j])

j++

}

}

}

Analysis:-

let hi - lo + 1 = n.

Clearly , partition involves only 1 while loop of length n and rest are just constants time seeking so, time taken by partition algorithm = O(n).

Recurrence relation:-

T(n) = c1 + c2 = O(1), if n = 1

= c1 + c3 + c4 + T(m-lo) + O(n) = T(m-lo) + O(n) , if n>1

or

=c1 + c3 + c4 + T(hi-m) + O(n) = T(hi-m) + O(n) , if n>1

so , in average case or best case:-

m - lo = hi-m = almost equal to (n/2)

so , T(n) = T(n/2) + n

solving using subsitution we get

= T(n/2²) + n/2 + n

= T(n/2³) + n/4 + n/2 + n

continuing like this k times we get

= T(n/2^k) + n( 1/2^k-1 + .... + 1/2 + 1)

it will stop when n/2^k =1 , k = log₂n

note (1/2^k-1 + .... + 1/2 + 1 ) is decreasing geometric progression . and always decreasing geometric progression = O(1))

so , T(n) = T(1) + n * O(1) = O(n)

Therefore , in average and best case T(n) = O(n)

Worst case:-

Here input array will be almost sorted or such that partition always keeps either left or right constant in number .

so , recurrence relation here reduces to T(n) = T(n-1) + n

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

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

= T(n-3) + n-2 + n-1 + n

k times we get

= T(n-k) + n-k+1 + ...+n-1 + n

it will stop when n-k = 1 so , k = n-1

= 1 + 2 + 3 ....+n

= n(n+1)/2 = O(n²)

Therefore in worst case T(n) = O(n²)