GeeksForGeeks analysis-of-algorithms Question 15

Question

In a modified merge sort, the input array is split at a position one-third of the length(N) of the array. What is the worst case time complexity of this merge sort?

Answer 1

The time complexity is given by:

If we use recursion tree first we have n elements then two subparts n/3 and 2n/3

 

Assume a tree here 

 

n divided in to n/3 and 2n/3

 

n/3 divided in to n/9 and 2n/9 ( this tree goes on left side and vanishes to 1 element)

 

2n/3 divided in to 2n/9 and 4n/9 ( here 4n/9 part grows even left side is vanished)

 

 so we will have time complexity based on deepest height 

 

and the elements in that is  n -->n/(3/2) ----> n/(3/2)^2 ---> n/(3/2)^3---> ..  1

 

Solving the above equation we get  = n * logn/log(3/2)  

                                                   = n logn/log(3/2)     

                                                   = N(logN base 3/2)

Importent Log Formulas : https://onlinemschool.com/math/formula/logarithm_formula/