T(n) = T(n/2) + clog(n) = O(log(n)^2)的归纳证明

Question

log() = log base 2 of ()
log()^2 = log^2 base 2 of ()

我被这个归纳证明困住了。我有以下递归关系

T(n) = T(n/2) + Theta(log(n))

我必须证明T(n) = O(log(n)^2)

使常量显式:

T(n) = T(n/2) + clog(n)

我知道对于0的定义，我必须找到k > 0和n' > 0，以便t(n) <= k(log(n)^2)对应每个n >= n'

T(n) = O(log(n)^2)假定为真对于每一个m < n，我有t(m) <= k(log(m)^2)为真:

在
T(n) <= k(n/2)(log(n/2)^2) + c log(n) =
= k(n/2)(log(n)^2 - 1) + c log(n)
= k(n/2)(log(n)^2)) - kn/2 + c log(n)。

k(n/2)(log(n)^2) - kn/2 + c log(n) <=? k(log(n)^2)<——这就是我卡住的地方

我找不到任何k或n，将使这工作，我在哪里做错了?

Answer 1

对于一些固定的α， M>T(n)≤α (log(n) + 1) log(n) + M，因为这个函数是O(log(n)²)你没有给我们一个基本情况，所以让我们假设这适用于足够小的n(而不会因为需要设置M而失去一般性)。

归纳步骤表明T(n/2)≤α (log(n/2) + 1) log(n/2) + M意味着T(n)≤α (log(n) + 1) log(n) + M，我们有

T(n)
= T(n/2) + c log(n)
≤ α (log(n/2) + 1) log(n/2) + M + c log(n)
= α log(n) (log(n) − 1) + M + c log(n).

如果设α = c/2，则

T(n)
≤ α log(n) (log(n) − 1) + M + 2 α log(n).
= α (log(n) + 1) log(n) + M.