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） ∈Θ（ ^n1.27635）