Is the answer option b i.e. **O(n ^{2.7})**

Dark Mode

407 views

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(n^{logb}^{a})=Thetha(n^{2.7095112913514545})