ALG3

3.4. Przykład 3: Wpadamy w pułapkę 63

Korzystając z powyższej uwagi oraz informacji zawartych w liniach komentarza możemy napisać:

uf    i    '

?’(«) = /<.+f„^2,«^+2r< +X(^/<-+²0 •

'=i V    ż

Po usunięciu sumy z wewnętrznego nawiasu otrzy mamy:

T{n) = /_c + l_u + £ (2/„ + 2/,. + i(/_c -t 2/„)).    (*)

/=i

Przypomnijmy jeszcze użyteczny wzór na sumę szeregu liczb naturalnych od I do N:

A'(N +1) o

1 I 2 + 3+---+jV =

Po jego zastosowaniu w równaniu (*) otrzymamy:

T(n) = t_e +t_a+2N{t_l, + /,) +

N(N +1)

(/, + 2/„).

Ostateczne uproszczenie wyrażenia powinno nam dać:

T(n) = /„(l + 3jV + N

^ oc ^A/"

+ 2,5/,. +——

... co sugeruje od razu, żc analizowany program jest klasy 0(n').

Ufff!

Nie było to przyjemne, prawda? A problem wcale nic należał do specjalnie złożonych. Nie zrażajmy się jednak trudnym początkiem, wkrótce okaże się, że można było zrobić to samo znacznie prościej! Do tego potrzebna nam będzie odrobina wiedzy teoretycznej, dotyczącej rozwiązywania równań rekurencyj-nych. Poznamy ją szczegółowo po ..przerobieniu” kolejnego przykładu zawierającego pewną pułapkę, której istnienie trzeba niestety co najmniej raz sobie uświadomić.