Question

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

iqsort(A, p, q){

if p ≥ q, return;

r=partition(A, p, q);

//run quick sort on the low part

quicksort(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 iqsort.

Answer 1

Given
qsort(A, p, q){

if p = q, return;

r=partition(A, p, q);

//run quick sort on the low part

quicksort(A, p, r - 1);//worst case O(n^2) //best,average case : O(nlogn)

//run insert sort on the high part

insertsort(A, r + 1, q); }//worst, average case O(n^2), best case:

qSort complexity is depended on the pivot choosen and order of the list:

Best case:O(nlogn)
explanation:
consider list is in sorted(increase), pivot is choose such that, list is divided into half
in that case
half part will be executed by quick sort which will run in (n/2)log(n/2)=O(nlogn)
and
another half part will be executed by insertion which runs in n/2 = O(n)//since list sorted
total complexity : nlogn +n = O(nlogn)
Worst and average case: O(n^2)
explanation:
consider list is in reverse sorted order, and last element is choosen as pivot,
the list not be divided evenly
quicksort will get 1 element, and insertion will get n-1 elements
insertion sort will take O(n^2) to sort reverse sorted list
hence complexity is O(n^2)