Question

I found a scrap of paper with this Java implementation of a sorting algorithm on it:

    // This will get me the Turing Award for sure!!
    public static void sort (int[] A) {
        sort(A, 0, A.length);
    } 

    // Sorts the subarray A[lo .. hi-1] into ascending order
    private static void sort (int[] A, int lo, int hi) {
        int size = hi - lo;
                  if (size == 2) {
            if (A[lo] > A[lo+1]) {
                int temp = A[lo];
                A[lo] = A[lo+1];
                A[lo+1] = temp;
            }
        }
        else if (size > 2) {
            int chunk = size / 3;
            sort(A, lo, hi-chunk);
            sort(A, lo+chunk, hi);
            sort(A, lo, hi-chunk);
        }        
    }

The recurrence relation for this algorithm is T(n) = a T(n/b) + O(n^d)

we know that a = 3

what is b?

what is d?

Use the Master Theorem to put the tightest possible upper bound on the running time of the algorithm.

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

Firstly this algorithm won't sort correctly since it has no merging of divided arrays.

So, for the sake of solving

It is

T(n)=3T(2*n/3)+O(n^0)

So, b=3/2 and d=0

Please note d is 0 since there is no merging of arrays

logb(a)=2.7095

Since f(n)=O(n^0)

SO, since c=0 c<2.7095

So, it is

T(n)=theta(n^(log_ba))=theta(n^(log1.5(3)))=theta(n^2.7095)

Kindly revert for any queries

Thanks.