Question

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

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.

Homework Answers

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/2k) + n/2k-1 + ... + n/2 + n

it will stop when n/2k =1 so , k = log2n

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

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

now , series 1+1/2 + 1/4 + 1/8 + 1/16 + .... + 1/2k-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(n2) where n is size.

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

putting all these in above , we get recurrence relation,

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

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

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

solving above using subsitution method:-

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

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

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

continuing like this k times we get

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

it will stop when n/2k =1 so , k = log2n

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

=O(1) + n2(1+1/22 + 1/42 + 1/82 + 1/162 + .... + 1/(2k-1)2)

now , series 1+1/22 + 1/42 + 1/82 + 1/162 + .... + 1/(2k-1)2 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) + n2 * O(1) = O(n2)

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

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(n2) 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(n2)

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

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Java : Modify the selection sort algorithm to sort an array of integers in descending order....
Java : Modify the selection sort algorithm to sort an array of integers in descending order. describe how the skills you have gained could be applied in the field. Please don't use an already answered solution from chegg. I've unfortunately had that happen at many occasion ....... ........ sec01/SelectionSortDemo.java import java.util.Arrays; /** This program demonstrates the selection sort algorithm by sorting an array that is filled with random numbers. */ public class SelectionSortDemo { public static void main(String[] args) {...
Suppose an array A stores n integers, each of which is in {0, 1, 2, ...,...
Suppose an array A stores n integers, each of which is in {0, 1, 2, ..., 99}. Which of the following sorting algorithms can sort A in O(n) time in the worst case? Question 16 options: A) merge sort B) counting sort C) quicksort D) None of these options is correct. E) insertion sort
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number in A and an O(log n)-time computation for each odd number in A. What is the best-case running time of Algorithm X? What is the worst-case running time of Algorithm X? 2. Given an array, A, of n integers, give an O(n)-time algorithm that finds the longest subarray of A such that all the numbers in that subarray are in sorted order. Your algorithm...
Let A[1..n] be an array of positive integers (A may not be sorted). Pinocchio claims that...
Let A[1..n] be an array of positive integers (A may not be sorted). Pinocchio claims that there exists an O(n)-time algorithm that decides if there are two integers in A whose sum is 1000. Is Pinocchio right, or will his nose grow? If you say Pinocchio is right, explain how it can be done in O(n) time; otherwise, argue why it is impossible.
First, understand the Selection-sort algorithm below: Selection-sort(A: Array [1..n] of numbers) 1       for i=n down to...
First, understand the Selection-sort algorithm below: Selection-sort(A: Array [1..n] of numbers) 1       for i=n down to 2 2                position=i 3                for j=1 to (i–1) 4                          if A[j]>A[position] then position=j 5                if position ≠ i then 6                          temp=A[i] 7                          A[i]=A[position] 8                          A[position]=temp (4 points) If input A=[12,5,11,6,10,7,9,8], what will A be after the 3rd iteration of the outermost for loop of the Selection-sort algorithm completes? A=[__, __, __, __, __, __, __, __] (8 points) Modify the algorithm to solve the...
Let A[1, . . . , n] be an array of n distinct numbers. If i...
Let A[1, . . . , n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A. 1. Which arrays with distinct elements from the set {1, 2, . . . , n} have the smallest and the largest number of inversions and why? State the expressions exactly in terms of n. 2. For any 0 < a < 1/2, construct an array for...
Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1]...
Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1] of real numbers if n = 1 return T[0] else temp ← Test (T[0..n − 2]) if temp ≥ T[n − 1] return temp else return T[n − 1] a. What does this algorithm compute? b. Set up a recurrence relation for the algorithm’s basic operation count and solve it.
Consider the following insertion sort algorithm. void insertion_sort(element a[], int n) // Put a[0]..a[n-1] into ascending...
Consider the following insertion sort algorithm. void insertion_sort(element a[], int n) // Put a[0]..a[n-1] into ascending order by insertion sort. { for (int k = 1; k < n; k++) { // At this point, a[0]..a[k-1] are already in order. // Insert a[k] where it belongs among a[0]..a[k]. You need to write code for this insertion as the body of the for-k loop. }//endfor k } a) Write the code for the body of the for-k loop to complete the...
2. Design a deterministic algorithm to solve the following problem. input: An array A[1...n] of n...
2. Design a deterministic algorithm to solve the following problem. input: An array A[1...n] of n integers. output: Two different indices i and j such that A[i] = A[j], if such indices exist. Otherwise, return NONE. Your algorithm must take O(n log(n)) time. You must describe your algorithm in plain English (no pseudocode) and you must explain why the running time of your algorithm is O(n log(n)).
Write a MIPS assembly program that sorts an array using bubble sort translating the C code...
Write a MIPS assembly program that sorts an array using bubble sort translating the C code int main(void) { int array[] = {10, 2, 7, 5, 15, 30, 8, 6}; // input array int arraySize = sizeof(array)/sizeof(array[0]); bool swapped = true; int j = 0; int tmp; while (swapped) { swapped = false; //Note : "j" , "arraySize - j" are optimizations to the bubble sort algorithm j++; // j= sorted elements int i=0; /* "arraySize - j" is used...