Asymptotische Ober- und Untergrenze finden?

Question

Wenn wir annehmen, dass T (n) für kleine n konstant ist, wie können wir die Lösung dieser Funktion finden?

T(n) = T(n−2) + 2logn 

Bisher bin ich nicht in der Lage, einen Weg zu finden, die ganze Funktion darzustellen. Kannst du mir bitte helfen? Ich möchte es wirklich verstehen.

Answer 1

Angenommen n ist gerade, und das T(1) = T(0) = 0.

T(n)/2 = log(n) + log(n-2) + ... + log(2) 
     = log((n/2)! * 2^n) 
     = n log(2) + log((n/2)!) 
     = n log(2) + n log(n) - n + O(log(n)) (Stirling's approximation) 

Also für n sogar, T(n) = Theta(n log(n)).

Für n ungerade, können Sie das T(n-1) < T(n) < T(n+1) beachten, und erhalten Sie die gleiche asymptotische gebunden.