in Algorithms retagged by
407 views
1 vote
1 vote
in Algorithms retagged by
407 views

2 Comments

Is the answer option b i.e. O(n2.7)

0
0

yes, the answer is O(n2.7), approach please!

0
0

2 Answers

1 vote
1 vote

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

2 votes
2 votes
1 answer
4