19,039 views
1 votes
1 votes

I was wondering whether the recurrence T(n) = T(n/2) + 2n could be solved by using master theorem, and what would be the way. I tried solving the recurrence but can't. There is no mention to it in CLRS book. Please help. Thanks in advance.

6 Answers

0 votes
0 votes

Ok so for the given function T(n) = T(n/2) + 2^n

for 2^n lets take its strict lower bound (nlogn)       

So the function becomes T(n) = T(n/2) + nlogn     and by masters theorem its time complexity comes out 0(nlogn)

 

Now lets take upper bound of 2^n i.e.  0(n^n)

so function becomes T(n) = T(n/2) + n^n       and by masters theorem its time complexity becomes 0(n^n)

 

Thus we can conclude that whenever the function is changed to its strictly lower or upper bound , the time complexity becomes equals to that function. Hence for the function T(n) = T(n/2) + 2^n    the time complexity equals 0(2^n)   

Related questions

1 votes
1 votes
2 answers
2
mdboi asked Oct 28, 2022
742 views
how do i apply master theorem to this? T(n)=2T(n/2)−n^3n
1 votes
1 votes
1 answer
3
0 votes
0 votes
2 answers
4
manvi_agarwal asked Aug 10, 2018
1,668 views
Solution using back substitution methodT(n) = 2T(n/2) + nlogn ?detailed solution please.ans is nlognlogn or n(logn)^2