Need help understanding Master Theorem in this proof

Question

I would really appreciate if someone could help me with a couple of questions,

For each of the following recursive function definitions, use the Master theorem to determine its asymptotic order of growth (i.e. Big-Tetha). If you think Master theorem is not applicable to a certain case, properly explain why. Can you still provide a somewhat reasonable upper bound (i.e. Big-O) for the running time in those cases? Note that base cases are all assumed to be constants.

(a) T (n) = T(n/2) + 2^n

(b) T (n) = 4T(n/2) +(n^1.5) − 1

(c) T (n) = T(n/3) + 100

(d) is T(n) = 125T(n/5) + n^3/logn

(e) T (n) = 2T(n/7) + log n + √n

I just read through some stuff online regarding this and I'm unable to gain enough of an understanding to answer this question. any help will be much appreciated, I'm trying to study for a test and I'm not getting any of this!

Thanks a lot!

Answer 1

All items except (a) are workable with the Masther theorem. In case (a), the toll function is not a polynomial and, thus, the Master theorem does not apply. But one can solve it by expansion:

T(n) = 2^n + T(n/2) 
     = 2^n + 2^(n/2) + T(n/4) 
     = 2^n + 2^(n/2) + 2^(n/4) + T(n/8)
     = ... 
     = O(2^n).

The result is clear by intepreting the recurrence as sums of binary numbers: 1+10+100+10000+10000000 <= 2*10000000.