edited by
6,980 views
1 votes
1 votes
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)
edited by

2 Answers

4 votes
4 votes
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

Related questions

0 votes
0 votes
3 answers
1
aditi19 asked Oct 6, 2018
1,127 views
what is the recurrence relation for merge sort?
0 votes
0 votes
0 answers
2
Rahul Ranjan 1 asked Jun 15, 2018
653 views
You are asked to sort 15 randomly generated numbers. One should prefer - 1. Bubble Sort2. Quick Sort3. Merge Sort4. Heap Sort Please explain why others 3 sorting algorith...