Wenn unsere Wiederholung die Form , müssen wir, um den "dritten Fall" der Master-Methode zu verwenden, den folgenden Halt haben:T.( n ) = a T.( n / b ) + f( n )
f( n ) = Ω (nLogba + ϵ) für einige und wenn für eine Konstante und alle ausreichend groß dann istϵ > 0a f( n / b ) ≤ c f( n )c < 1nT(n)=Θ(f(n))
Unsere Wiederholung ist definiert als
T(n)=3T(n/4)+nlogn.
Per Definition haben wir .a=3,b=4,f(n)=nlogn
Wir müssen nun zeigen, dass polynomiell größer als . Das ist der Teil " " von oben. Durch Definieren von erreicht. Der Grund dafür ist, dass und .f(n)nlogbaf(n)=Ω(nlogba+ϵ)ϵ≈0.2log43≈0.793f(n)=Ω(n0.793+ϵ)
Wir müssen zeigen, dass die Regelmäßigkeitsbedingung erfüllt. Das ist der Teil " für eine Konstante und alle ausreichend großen ".f(n)af(n/b)≤cf(n)c<1n
Wir stecken einfach unsere Werte von , um zu erhalten:Wir haben nur das " " in und " " eingesteckt.a,b
af(n/b)=3(n/4)log(n/4).
nf(n)n/4
Um dies besser sichtbar zu machen, sei und beobachte, dass . Wenn wir mit tauschen, haben wir wobei .k=n/4af(k)=aklogkkn/4
3(n/4)log(n/4)≤(3/4)nlogn=cf(n)
c=3/4
Damit sind unsere notwendigen Anforderungen erfüllt und wir haben .T(n)=Θ(nlogn)