Time complexity of code given

Question

Comments

Note that t1 and t2 divide the array into three equal parts.

When low equals high or low+1 equals high,constant time is taken.

Else sorting is called thrice on two third part of an array.

We obtain a recurrence relation like

S(n)=3S(2/3n)+Θ(1), where n is the current length of the array or in other words high - low +1

S(2)=S(1)=Θ(1)

Look at the recurrence and its base condition, we can apply master's theorem and obtain,

Θ(n^log_3/23)= Θ(n^2.7095)  [Case 1 of master's theorem]

---

should that 2nd or middle call to sorting() be

$sorting(A,t_{\color{red}{1}},high)$

instead of

$sorting(A,t,high)$

?

---

@GateAspirant999

While reading I saw it as t1 instead of t :-P

I have solved this question before it should be t1 (t1 to high)

Answer 1

I think answer is 5.7