Can we solve the recurrence T(n) = T(n/2) + 2^n by masters theorem, if possible?

Question

I was wondering whether the recurrence T(n) = T(n/2) + 2ⁿ 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.

Comments

https://gateoverflow.in/243824/made-easy-booklet?show=244475#c244475

 

Answer 1

master theorem provide wrong solution for polynomial function

Comments

This is not a polynomial function but an exponential function.

Answer 2

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)