geeksforgeeks

Question

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

A	N(logN base 3)
B	N(logN base 2/3)
C	N(logN base 1/3)
D	N(logN base 3/2)

Comments

Can Sombody provide the solution for this recurrance relation ? this will be the recurance eqn for this que...

 T(N) = T(N/3) + T(2N/3) + N

---

D will be the answer to it. You can apply the tree method of solving recurrence relation, and you’ll realize that the most extended branch of the tree will have log n (base 3/2) length. Now, each level of the tree has a cost of n (total merge cost) and for the upper bound case, the tree has log n (base 3/2) levels and each level has cost n. Hence total cost is n*log n (base 3/2).

 

 

 

Answer 1

Answer is D.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).

 

Tree we have to assume I don't understand how to draw here

Comments

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

how we can come to this conclusion ,

can you please explain in a broader way

 

thanks in advance

Answer 2

$\therefore$ Answer : $(D)$