复发T（N）的= T（N/3）+ T（2N/3）

Question

我在网上搜索到了这一点，但我似乎只找到一个类似的公式答案：

T(n) = T(n/3) + T(2n/3) + cn 

但一个我试图解决的是：

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

基本情况：我们可以假设T(a) = Theta(1)任何常量a。

我成功地证明了（通过归纳）T(n) = O(n*log(n))。我认为答案应该是Theta(n*log(n))，但我不能证明T(n) = Omega(n*log(n))。

所以我的问题是 - 我正确的答案是O(n*log(n))，而不是Theta(n*log(n))？如果这是真的，真的会很大......

如果我错了，我当然会说明在何处我卡在感应过程...

谢谢！

P.S.如果您需要，请尝试使用归纳解释，因为我还没有学习解决这些问题的所有方法。

Answer 1

由于T（n）= n满足基本情况和递归，所以你不能证明它是Omega（n log n）。