Problemy z obliczaniem złożoności

Hej. Jutro mam kolokwium z ASD :). I mam problem ze zrozumieniem wyliczania złożoności. Mianowicie chodzi mi o notację asymptotyczną. Wiem np., że Theta jest jest to po prostu usunięcie funkcji wyższego i niższego rzędu, ale jak dostanę zadanie:Korzystając z definicji, określ czy prawdziwe jest założenie: 4n^{2}+4n+4 = \Theta(n^{2}) , to chociaż wiem, że to jest prawdziwe to nie wiem jak to mam zrobić z definicji.

Plus twierdzenie o rekurencji uniwersalnej. Wiem na czym polega, ale kiedy mam wybrać odpowiednie warunki? Np skąd wiadomo, że dla T(n) = 9T(n/3) + n należy skorzystać z pierwszego warunku? Podstawiam a = 9 b = 3 liczę logarytm, ale nie wiem, który warunek wybrać.

Ad.1. Najprościej będzie to udowodnić licząc odpowiednią granicę. Popatrz na tą tabelkę:
http://pl.wikipedia.org/wiki/Asymptotyczne_tempo_wzrostu#Zale.C5.BCno.C5.9Bci_algebraiczne_O.2C_o.2C_.CE.A9.2C_.CF.89.2C_.CE.98

Tylko, że my jeszcze nie zaczęliśmy granic liczyć. Zaczną się od drugiego semestru, więc to raczej nie o to chodzi ;/

o_O? Takie granice to w liceum liczyliśmy...
No ale jak chcesz sobie utrudniać życie, to musisz w takim razie dowodzić bardziej łopatologicznie, tzn musisz pokazać że
istnieją takie n0, c1 i c2 że dla każdego kolejnego n większego od n0 masz spełnioną odpowiednią nierówność. Jeśli chcesz pokazać że

4n^{2}+4n+4 = \Theta(n^{2})

to musisz pokazać że można tak wybrać n0, c1 i c2 że
c1 * n² < 4*(n²+n+1) < c2 * n²
Jako ze warunek brzmi "istnieje" to wystarczy pokazać przykład, więc mamy c1 = 1 i wtedy zawsze n² < 4(n²+n+1) dla n > 0
Druga strona nierówności jest trochę trudniejsza bo musimy rozwiązać tą nierówność wprost, ale znów pamiętajmy o tym że mamy wygodny warunek dla n, tzn to musi być prawdziwe tylko począwszy od jakiegoś n.
Zakładamy więc sobie dla wygody c2 = 5 i mamy:
4n² + 4n + 4 - 5n² < 0
n² - 4n + 4 - 8 > 0
(n-2)² > 8
n > sqrt(8)+2
n > 5

Pokazaliśmy więc że dla c1 = 1, c2 = 5 i n0 = 5 nierówność jest spełniona ;]

Okej, dzięki chyba rozumiem. Ale tam powinno być chyba 4n²+4n+4-5n² < 0 zamiast 4n²+4n+1-5². A twierdzenie o rekurencji już ogarnąłem ;).