algorithm - 下限和上限

Question

我有以下递归关系：

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

并且不能完全弄清楚正确的下限和上限。
对于我所做的上限：

T(n) = 2T(n/3) +5T(n/3) +n = 7T(n/6) +n

其中，根据主定理应该是：n ^{log ₆ 7}

对于下限，我做了：

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

其中，根据主定理应该是：n ^{log ₃ 7}

但是，当解决它时，我只得到了部分分数，因为“有更好的界限”
我做错了什么？

Answer 1

T(n)=2*T(n/3)+5*T(n/6)+n

Let
T(n)=c*n^k+o(n^k)

Then
c*n^k+o(n^k)=2*c*(n/3)^k+o((n/3)^k)+5*c*(n/6)^k+o((n/6)^k)+n  

c/6^k*(6^k-2^(k+1)-5)=o(n^k)

k=1.27635...

所以，T(n) ≃ c*n ^1.27635

T(n) ∈ Θ(n ^1.27635 )