master theorem 推导

Let a $\geq$ and b > 1 be constants, let f(n) be a function, and let T(n) be defined on the nonnegative integers by the recurrence
$T(n) = aT(n/b) + f(n)$ ,
where we interpret n/b to mean either $\lfloor n/b \rfloor$ or $\lceil n/b \rceil$ . Then T(n) has the following asymptotic bounds:

If $f(n) = O(n^{log_ba-e})$ for some constant e > 0, then $T(n) = \theta(n^{log_ba})$ .
If $f(n) = \theta (n^{log_ba})$ , then $T(n) = \theta(n^{log_ba}log\,n)$ .
If $f(n) = Ω(n^{log_ba+e})$ for some constant e > 0, and if $af(n/b) \leq cf(n)$ for some constant c < 1 and all sufficiently large n, then $T(n) = \theta(f(n))$

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

当 $f(n) = \theta(n^{log_ba})$ 的时候，
$T(n/b) = aT(n/b^2) + f(n/b)$
$f(n/b) = cn^{log_ba}/a$
$af(n/b) = f(n)$

于是第二种就说的通了

第一种情况的话
$f(n/b) \leq cn^{log_ba-e}/(a-e)$
$af(n/b) \leq \frac{a}{a-e}n^{log_ba-e} = \frac{a}{a-e}f(n)$
所以是一个等比数列 $q = \frac{a}{a-e}$
$f(n)(1+q+q^2 + ... + q^{log_bn}) = f(n)\frac{1-q^{log_bn}}{1-q}$ = $f(n)\frac{q^{log_bn}-1}{q-1}$ < $f(n)\frac{q^{log_bn}}{q-1}$ = $f(n)\frac{n^{log_bq}}{q-1}$ = $f(n)\frac{n^{log_ba-log_b{a-e}}}{q-1}$ = $cn^{log_ba-e}\frac{n^{log_ba-log_b{a-e}}}{q-1}$ = $c\frac{n^{log_ba}}{q-1}$
于是第一种也说的通

对于第三种情况
$f(n/b) = n^{log_ba+e}/(a+e)$
$af(n/b) = \frac{a}{a+e}n^{log_ba+e} = \frac{a}{a+e}f(n)$
所以是一个等比数列 $q = \frac{a}{a+e}$
$f(n)(1+q+q^2 + ... + q^{log_bn}) = f(n)\frac{1-q^{log_bn}}{1-q}$ < $f(n)\frac{1}{1-q}$
第三种情况也说的通，但是我不理解为什么会要特别强调if $af(n/b) \leq cf(n)$ for some constant c < 1，我觉得只要e大于0，这样的c是一定可以找到的

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

$T(n) = Θ(n^{log_ba})$ when $f(n) = O(n^{log_ba-e})$
T(n) = Θ(n
logb a
log n) when f(n) = Θ(n
logb a
)
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