retagged by
648 views
1 votes
1 votes
retagged by

2 Answers

1 votes
1 votes

t1 and t2 divide array passed to the function into 3 parts.

low to t1 is first 1/3rd part, t1 to t2 second 1/3rd part and t2 to hight last 1/3rd

 

Note that:

Low to t2 is 2/3rd

t1 to high is 2/3rd

T(n)=3T(2n/3)+O(1)

Using masters theorem

a=3, b=3/2

T(n)=Thetha(nlogba)=Thetha(n2.7095112913514545)

0 votes
0 votes

Answer is option b i.e. O(n2.7). Here's the explanation :-

Related questions

0 votes
0 votes
1 answer
1
manvi_agarwal asked Sep 3, 2018
1,026 views
Is the answer to this solution is O( n2 log (n) ) or O( n log (n) )
0 votes
0 votes
0 answers
4
iarnav asked Jan 12, 2018
548 views
in questions like how many multiplications of n are needed are being solved by dividing n into n/2 * n/2 and then end up with recurrence t(n) = t(n/2) + O(1) How to reach...