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:
- If
for some constant e > 0, then
.
- If
, then
.
- If
for some constant e > 0, and if
for some constant c < 1 and all sufficiently large n, then
首先 如果一共有k+1行 n = bk k = logbn, 一共有logbn +1行
当的时候，
于是第二种就说的通了
第一种情况的话
所以是一个等比数列
=
<
=
=
=
=
于是第一种也说的通
对于第三种情况
所以是一个等比数列
<
第三种情况也说的通，但是我不理解为什么会要特别强调if for some constant c < 1，我觉得只要e大于0，这样的c是一定可以找到的
然后再看一下算法课上讲的
when
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
