Nehmen wir der Einfachheit halber an 5 teilt n
und das n / 2 = n - 5 k für eine ganze Zahl k > 0.
T.( n )T.( n )T.( n )= T.( n - 5 ) + cn2= cn2+ c ( n - 5)2+ c ( n - 10)2+ c ( n - 15)2+ . . . + c52+ c02= c (n2+ ( n - 5)2+ ( n - 10)2+ ( n - 15)2+...+52+02)≥c(n2+(n−5)2+(n−10)2+(n/2)2)≥c(n/2)(1/5)(n/2)2)=cn3/40=(c/40)n3=Ω(n3)=cn2+c(n−5)2+c(n−10)2+c(n−15)2+...+c52+c02≤c(n/5)n2≤cn3=O(n3)
Wir schließen daraus T(n)=Θ(n3).
Let's assume for simplicity that n/2=n−2k for an integer k>1.
T(n)T(n)=T(n−2)+logn=logn+log(n−2)+log(n−4)+...+log(4)≥logn+log(n−2)+log(n−4)+...+log(n/2)≥(n/2)log(n/2)=Ω(nlogn)=T(n−2)+logn=logn+log(n−2)+log(n−4)+...+log(4)≤(n/2)logn=O(nlogn)
We conclude that T(n)=Θ(nlogn).