0 votes 0 votes Algorithms algorithms sorting time-complexity numerical-answers test-series + – GateAspirant999 asked Sep 16, 2018 retagged Jul 17, 2022 by makhdoom ghaya GateAspirant999 940 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply sakharam commented Sep 16, 2018 reply Follow Share 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, Θ(nlog3/23)= Θ(n2.7095) [Case 1 of master's theorem] 1 votes 1 votes GateAspirant999 commented Sep 17, 2018 reply Follow Share should that 2nd or middle call to sorting() be $sorting(A,t_{\color{red}{1}},high)$ instead of $sorting(A,t,high)$ ? 0 votes 0 votes sakharam commented Sep 17, 2018 reply Follow Share @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) 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes I think answer is 5.7 rajatmyname answered Sep 18, 2018 rajatmyname comment Share Follow See all 0 reply Please log in or register to add a comment.