Consider a version of merge sort in which an array of size n

Consider a version of merge sort in which an array of size n is divided into 3 segments of sizes n/3. Write the recurrence relation for the time complexity and solve it. (Show all your work. You can assume n = 3^k, and T(1)=1.)

Please show all your work. I will rate quality answers. Thank you!

Solution

When, merge sort in which an array of size n is divided into 3 segments of sizes n/3.

1. That means we have 3 Subproblems of size n/3
2. Merging two subproblems still take O(n) time.


So the recurrance relation will be

T(n) = 3T(n/3) + n
We can solve it using Masters Theorem
a = 3, b = 3
n^{log₃ 3}    => n¹

f(n) = n = n^{log₃ 3}   
=> T(n) = O(n log n)


Thanks, let me know if there is any concern.