Question

Assume L is an array, length(L) returns the number of records in the array, and qsort(L,i,j) sorts the records of L from i toj (leaving the records sorted in L) using the Quicksort algorithm. What is the average-case complexity for the following code fragment? for (i = @; i<length(L); i++) asort(1, 0, 1); Consider the time for each pass of the for loop, and sum them all together. Prove the upper and lower bound, then argue for an average case. You should provide a formula for computing the total execution time and then determine the asymptotic complexity. Show all your work.

Answer 1

Let we go for complexity for quicksort algorith then we solve for complexity of the given code.

QuickSort Algorithm:

     public qsort(L,i,j){ // l is length of array
         if(i < j){
             pi = partition(L,i,j); (l times) // partition function will place arr[pi] at there correct place.
             qsort(L,i,pi - 1);  // based on array type it (Sorted/unsorted), its time complexity differs
             qsort(L,pi + 1,j);  // if sorted then T(l -1) else say for random T(l/2)
         }
     }
    public void partition (arr[], low, high){
    pivot = arr[high];  
    int  i = (low - 1) ;
    for (int j = low; j <= high- 1; j++){ // L times will run
        if (arr[j] < pivot){
            i++;  
            swap (arr[i] and arr[j]) // 1 time
        }
    }
        swap (arr[i + 1] and arr[high]);
    return (i + 1); // overall l time will take
    }

Therefore , let the array be sorted the overall time complexity come out to be

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

= O(l²)

In case array is randomised then

T(l) = 2T(l/2) + l

= O( l * log(l))

We have to find the total time execution for the following code

for(i = 0; i < length(L); i++ ) // this will run length(L) times , say length(L) be l.

qsort(L, 0 , i);

when i = 0,

qsort(L,0,0) will sort single element which is already sorted.

when i = 1,

qsort(L,0,1) will sort the already sorted upto index 0 array

when i = 2,

qsort(L,0,2) will sort the already sorted (upto index 1) array

when i = 3,

qsort(L,0,3) will sort the already sorted (upto index 2) arry

... as so on.

Now from the above we see that, quick sort has array which has already sorted array exept the last index which needs to be placed at right position.

For derivation of formula,

this for loop will run l times and say array is sorted

Then execution time will be derived as,

T(l) = l * (T(l-1) + l )

Upper Bound execution time calculation,

This will happen in case array is sorted

T(l) = l * (T(l-1) + l)

T(l) = l * (O(l²))

= O(l³)

For Lower Bound time calculation,

Since the array comes to quick sort is already sorted misplaces at only last index,

qsort(L,i,j) = T(l) = T(l-1) + l

In this case also, overall T(l) = l * (T(l-1) + l) = O(l³)

In either case asymtotic complexity is O(l³).

Hope you like this answer. In case any doubt comment it. Vote up thanks.