Master Theorem und Exponentialfunktionen

Question

Ich kam vor kurzem über einige Übungen zum Master-Theorem und der Art. Man diktierte, dass wir das Θ() einiger Ausdrücke finden (gegeben Τ (1) = Θ (1)). Die meisten waren mit dem Meister Theorem gelöst, aber dieses

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

offensichtlich nicht so gelöst, da es nicht die allgemeine Form des Satzes ist.
Wie finden wir das Θ() davon?

Answer 1

Sie können die Serie teleskopieren, um relativ einfach eine Lösung zu finden. Es ist Theta(log n) egal die Macht in der Rekursionsbeziehung (vorausgesetzt, es ist weniger als eins). Hier mit c statt 5/6.

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) 

Trivial T(n) >= log n, so T(n) = Theta(log n).