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!

有帮助吗?

解决方案

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.

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top