Zadanie indukcyjne.

Dobry wieczór wszystkim :) To jest akurat mój pierwszy post ale mam problem...bardzo proszę sprawdzić moje rozwiązanie:

T(n)=4T(n/2)+n

1. Zauważmy

T(1)= tetha(1)

1. Założenie weźmy np n^2

T(n)=n^2
Zatem

T(k)=ck^2 dla k<n

Okej no to lecimy

T(n)=4c(n/2)^{2 +n=cn}2+n i to wyrażenie ma być <=cn^2 Co jest nie prawdą, ale...

cn^{2 -(cn}2-n)<= cn^{2 Jeżeli cn}2-n>=0

Zatem odpowiedź to T(n)=tetha(n^2)

Bardzo proszę o sprawdzenie i ewentualne poprawki.

1. Wiesz jakie możesz dostać najtrudniejsze pytanie na egzaminie ? Sformułuj pytanie i na nie odpowiedź.
   1.1. Myślę, że chodzi CI o rozwiązanie tej rekurencji... możesz to zrobić metodą odgadnięcia albo poczytać o teorii równań różnicowych skończonych (polecam).
2. Zakładasz, ze k = n^2 // dla wygody podczas dzielenia...
   Więc dalej piszesz T(k) = 4(T(k/2)) + k = 4(4T(k/4) + k/2) + k = ... // aż dojdziesz do T(1) wszystko porządkujesz liczyć sumę częściową szeregu itp.
   dostajesz wzór, który wypada dowieść indukcyjnie. Następnie możesz go oszacować asymptotycznie.