self doubt

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?

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

Comments

I am getting D.. What is the correct one?

---

I think you are right. In worst case it should be option d

---

@abhishekh if it is said to split at 1/4 then answer would be $nlog_{4/3}n$

Answer 1

Answer would be D)

N(logN base 3/2)

 

recurrence would be T(N) = T($\frac{N}{3}$) + T($\frac{2N}{3}$) + N

solve it using tree so $\frac{2^kN}{3^k}$= 1 at at K+1 level so,k=$log_\frac{3}{2}$n

at each level workdone is n so n+n+n+.....(k+1)time ,

$n*(k+1)$=$n$*($log_\frac{3}{2}$n+1)=$\theta($n$log_\frac{3}{2}$n)