如何解决以下递推关系？

Question

这道题是在考试中出现的，我不知道该怎么做，谁能帮助我或给点提示。我觉得大师的方法在这里不适用？请帮忙。

T(n)=T(n/2)+ θ(logn)

Answer 1

假设 n 是 2 的幂，比如 n = 2^k，为了简单起见，我们假设 T(n) = T(n/2) + lg(n) 其中 lg 是对数底数 2, 和 T(1) = lg(1) = 0.

T(n) = lg(n) + lg(n/2) + lg(n/4) + ... + lg(1)
     = lg(2^k) + lg(2^{k-1}) + ... + lg(2^0)
     = k.lg(2) + (k-1)lg(2) + ... + 0.lg(2)
     = (k + (k-1) + ... + 0) lg(2)
     = k(k+1)/2
     = lg(n)(lg(n)+1)/2
     = Theta(lg(n)^2).

因为 n 不是 2 的幂，可以注意到 T 是递增函数，因此 T(2^k) <= T(n) <= T(2^{k+1}) 其中 k = floor(lg(n))。从上面的确切结果，我们得到

k(k+1)/2 <= T(n) <= (k+1)(k+2)/2

等等

T(n) = Theta(floor(lg(n))^2) = Theta(lg(n)^2)

如何解决以下递推关系？

How to solving below recurrence relation?

algorithm

recurrence

master

theorem