Wie kann ich T (n) in asymptotischer Schreibweise für Rekursionen angeben?

Question

Ich brauche T (n) in asymptotischer Notation für folgende Rekursion geben:

T(n) = 2T(n/2) + *big_omega(n) 
T(n) = T(n-1) + *big_omega(n) 

und möglicherweise die Argumentation erklären? Dank

Answer 1

Verwenden Master-Theorem

1) n = O (n^log_n (n)) -> Case 1

Verwenden

2) T (n) = T Abrollen (n -1) + O (n)

T (n-1) = T (n-2) + O (n-1) -> T (n) = T (n-2) + O (n-) 1) + O (n)

...

versuchen, eine Form eine nicht rekursive Formel

zu bilden