Question

Let mixsort(A, 1, n) be an algorithm that sorts an array A with n integers. It works as follows:

mixsort(A, p, q){

if p ≥ q, return;

r=partition(A, p, q);

//run mixsort on the low part

mixsort(A, p, r − 1);

//run insert sort on the high part

insertsort(A, r + 1, q);

}

Compute the best-case, worst-case, and average-case complexities of mixsort.

Answer 1

mixsort(A, p, q)//suppose it takes time = T(n) , where n = q-p+1

{

if p ≥ q, return;//it takes O(1) time

r=partition(A, p, q);// it is very well that it takes Time = O(q-p+1) = O(n)

//run mixsort on the low part

mixsort(A, p, r − 1);//clearly it takes time = T(r-1-p+1) = T(r-p)

//run insert sort on the high part

insertsort(A, r + 1, q);//suppose it takes time = S(q-(r+1)+1) = S(q-r)

}

From above ,we can write recurrence relation:-

T(n) = O(1) , if n = 1

= T(r-p) + S(q-r) + O(n) , if n>1

Best case complexity:-

In best case , we know that the partition algorithm divides the array to be sorted into almost two equal parts of size n/2.and also insert sort also takes best case time which is O(n) where n is size.

so, T(r-p) becomes T(n/2) and S(q-r) becomes O(n) .

putting all these in above , we get recurrence relation,

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

for simplicity assume that O(n) + O(n) = n

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

solving above using subsitution method:-

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

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

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

continuing like this k times we get

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

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

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

=O(1) + n(1+1/2 + 1/4 + 1/8 + 1/16 + .... + 1/2^k-1)

now , series 1+1/2 + 1/4 + 1/8 + 1/16 + .... + 1/2^k-1 is decreasing Geometric progression , so series = O(1)

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

best case complexity T(n) = O(n)

Average case complexity:-

In best case , we know that the partition algorithm divides the array to be sorted into almost two equal parts of size n/2.and also insert sort also takes average case time which is O(n²) where n is size.

so, T(r-p) becomes T(n/2) and S(q-r) becomes O((n/2)²) = O(n²)

putting all these in above , we get recurrence relation,

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

for simplicity assume that O(n²) + O(n) = O(n²) = n²

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

solving above using subsitution method:-

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

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

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

continuing like this k times we get

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

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

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

=O(1) + n²(1+1/2² + 1/4² + 1/8² + 1/16² + .... + 1/(2^k-1)²)

now , series 1+1/2² + 1/4² + 1/8² + 1/16² + .... + 1/(2^k-1)² is decreasing Geometric progression with common ratio r=1/4 , and decreasing geometric progression series always T(n) = O(1)

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

Average case complexity T(n) = O(n²)

Worst case case complexity:-

In worst case , we know that the partition algorithm divides the array to be sorted into two parts of size O(c) and O(n-c).and also insert sort in worst case also takes a worst time which is O(n²) where n is size.

suppose c = 1, then

so, T(r-p) becomes T(n-1) and S(q-r) becomes S(1) . we know that insertion sort takes S(1) in worst case which is O(1)

putting all these in above , we get recurrence relation,

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

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

for simplicity assume that O(1) + O(n) = O(n) = n

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

solving above using subsitution method:-

T(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

continuing like this k times we get

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

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

putting the value of k , we get

= T(1) + 2 + 3 + 4 + 5 +6 + .... + n

=O(1) + 2 + 3 + 4 + 5 +6 + .... + n

= 1 + 2 + 3 + 4 + 5 +6 + .... + n

now , series 1+2 + 3 + 4 + 5 +6 + .... + n = n(n+1)/2

so , T(n) =n(n+1)/2 = O(n²)

Worst case complexity T(n) = O(n²)