algorithm - Q : Recurrence relation by Substitution

Question

我有递推关系:T(n) = c*T (n/3) + (c/2)*n对于任何 c

让 T(n) >= n^1.5 成为替代方法的猜测。

Answer 1

假设T(n) <= n^1.5是正确的道路。有了它，我们可以:

T(n) <= 6 ( n^1.5 / 3^1.5 ) + 3n = (6 / 3^1.5)* n^1.5 + 3n .

6/3^1.5是 5.1... 但现在暂且称它为 a .所以我们有:a*n^1.5 + 3n .

我们需要证明对于 n0>n c*n^1.5 > a*n^1.5 + 3n 存在 c > 0 .首先让除以 n:c*n^0.5 > a*n^0.5 + 3产量:(c-a)*n^0.5 > 3 .

从这里可以清楚地看出，您可以选择任何 c > a和 n > 9所以这是真的。

总结一下:我们得到了 T(n)大于 T'(n) = (6/3^1.5)*n^1.5 + 3n并证明对于 c > 6/3^1.5和 n > 9 T(n) < cg(n) where g(n) = n^1.5