マスター定理と指数関数

Question

私は最近、マスター定理とソートに関するいくつかのエクササイズを行ってきました。 いくつかの式（Τ（1）=Θ（1）で与えられる）のΘ（）が見つかるように指示しました。 大半は、マスター定理で解決されたが、それは定理の一般的な形式ではありませんので、この1

T(n)=T(n^(5/6))+Θ(logn) 

は明らかに、そのように解決されていません。
どのようにΘ（）を見つけるのですか？

Answer 1

比較的簡単に解決策を見つけるために、望遠鏡を望遠鏡で見ることができます。繰り返し関係のパワーに関係なく（1未満であると仮定して）、Theta(log n)です。ここでは5/6ではなくcとなります。

T(n) = T(n^c) + log n 
    = log n + log(n^c) + log(n^(c^2)) + log(n^(c^3)) + ... 
    = (1 + c + c^2 + ...)(log n) 
    <= (log n)/(1 - c) 

自明T(n) >= log n、そうT(n) = Theta(log n)。