math - 通过证明递归不是 O(n) 的归纳证明是 Omega(nlogn)

Question

注意：这与家庭作业有关。

我试图证明这一点T(n/3) + T(2n/3) + n >= cn , for all c > 0。

当我尝试这样做时，基本情况失败(T(1) = 1 >= cn, for all c > 0，不正确）。所以为了解决这个问题，我想表明问题的下限高于O(n). 这是否构成正确的证明？

Answer 1

作为提示，请尝试添加更多术语。假设你的函数满足

T(n) ≥ k ₁ n log n + k ₂ n + k ₃

_{现在，当您插入 n = 1 时，可以通过适当设置 k 2}和 k ₃使右侧非零。这种技术对于对上限和下限函数使用归纳法很常见并且很有效，因为这些低阶项与大 O 表示法无关，并且可以优雅地处理较小的情况。