master theorem 推导

Let a and b > 1 be constants, let f(n) be a function, and let T(n) be defined on the nonnegative integers by the recurrence
,
where we interpret n/b to mean either or . Then T(n) has the following asymptotic bounds:

1. If for some constant e > 0, then .
2. If , then .
3. If for some constant e > 0, and if for some constant c < 1 and all sufficiently large n, then

首先 如果一共有k+1行 n = b^k k = log_bn, 一共有log_bn +1行

当的时候，

于是第二种就说的通了

第一种情况的话


所以是一个等比数列
= < = = = =
于是第一种也说的通

对于第三种情况


所以是一个等比数列
<
第三种情况也说的通，但是我不理解为什么会要特别强调if for some constant c < 1，我觉得只要e大于0，这样的c是一定可以找到的

然后再看一下算法课上讲的

1. when

2. T(n) = Θ(n
   logb a
   log n) when f(n) = Θ(n
   logb a
   )

3. T(n) = Θ(f(n)) when f(n) = Ω(n
   logb a+�) for some � > 0 and
   af(n/b) < cf(n) for some c < 1 when n sufficiently large