Na dzisiejszych zajęciach rozbudujemy bardziej ostatni wykład. Na początek nieco pojęć podstawowych. Algorytmika to dziedzina wiedzy zajmująca się badaniem algorytmów. Algorytm z kolei potocznie może być rozumiany jako pewien przepis na wykonanie zestawu czynności prowadzących do osiągnięcia oczekiwanego i z góry określonego celu. Mówi się także, że algorytm jest pewną ściśle określona procedura obliczeniową, która dla zestawu właściwych danych wejściowych generuje okreslone dane wyjściowe. Ostateczne uoglónione znaczenie słowa algorytm brzmi, że algorytm to zbiór reguł postepowania umozliwiających rozwiązanie określonego zadania w kończonej liczbie kroków, czyli skończonym czasie. Słowo to pochodzi z łaciny od słowa algorism co w śreniowieczu znaczyło sztukę rachowania na liczbach w systemie dziesiętnym. Słowo to utworzono od nazwiska perskiego matematyka z XI wieku n.e. Muhameda al Choresmi - twórcy systemu dziesiętnego. Algorytm może być rozumiany jako pewne odwzorowanie f, które dla okreslonego zestawu danych wejściowych We generuje okreslony zestaw danych wyjściowych Wy, czyli:

. Każdy algorytm działa na pewnym zbiorze obiektów na przykład liczb wykonując na tych obiektach pewne operacje. Zbiór obiektów wraz z operacjami wykonywanymi na tych obiektach nosi nazwę dziedziny algorymicznej. Teraz nieco o samych sposobach zapisu algorytmu. Opis algorytmu obejmuje precyzyjny opis kolejnych jego kroków. Do przedstawienia algorytmu stosuje się zwykle opis werbalny, jak również zapis formalny w postaci zapisów graficznych (schematów blokowych), formalnych specyfikacjach programów (VDM), w postaci pseudokodu, oraz zapis algorytmu w dowolnym języku programowania. Język programowania jest srodkiem umożliwiającym zapis algorytmów w postaci zrozumiałej dla człowieka, a równocześnie przetwarzalnej do postaci zrozumiałej dla komputera. Zapis algorytmu w języku programowania jest traktowany jako zapis formalny. Program komputerowy może być uznawany za jeden z rodzajów modeli matematycznych. A więc to wygląda tak, że kod żródłowy programu (w języku programowania) jest przetwarzany w kod wynikowy programu napisany w języku maszynowym. Teraz parę słów o klasyfikacji algorytmów. Rozważać będziemy trzy klasy algorytmów: sekwencyjne i równoległe, numeryczne i nienumeryczne, oraz rekurencyjne i iteracyjne. Skupimy się na początek na tych dwóch ostatnich. Rekurencja oznacza wywołanie funkcji (procedury) przez tę samą funkcję (procedurę). Istnieje jedna Niepożądana cecha definicji rekurencyjnych. Aby wyznaczyć entą wartość, trzeba najpierw wyznaczyć wszystkie wcześniejsze wartości. Ważne jest, aby kolejne wywołania funkcji (procedury) rekurencyjnej były realizowane dla kolejnych wartości parametrów formalnych w taki sposób, aby nie doszło do zjawiska nieskończonej pętli rekurencyjnych wywolań funkcji. Na stronie nastepnej został przedstawiony stos programu w wywołaniach rekurencyjnych (przykład z C/C++). Z kolei teraz omówimy sobie jedną z funkcji rekurencyjnych, a mianowicie funkcję odnosząca się do ciągu Fibonacciego. Enty wyraz ciągu Fibonacciego obliczany jest według nastepującej formuły:

A oto, jak wygląda implementacja rekurencyjna w języku C takiej funkcji:

long int Fib (int n)

{

if (n<2) return n;

else return Fib(n-2)+Fib(n-1);

}

Teraz zobaczmy na gotowy program obliczający liczbę Fibonacciego dla danego n:

#include <stdio.h>

#include <time.h>

long int RekurencyjnyFib(long x)

{

int wynik=0;

if (x < 2 && x>=0)

wynik=x;

else

wynik=RekurencyjnyFib(x-1) + RekurencyjnyFib(x-2);

return wynik;

}

main()

{

struct tm *czas_pocz, *czas_koncowy;

time_t t1, t2;

long liczba, wynik;

printf("Program obliczajacy n-ty wyraz ciagu Fibonacciego \n");

printf("\nPodaj liczbe n= ");

scanf("%d", &liczba);

t1=time(NULL);

czas_pocz=localtime(&t1);

printf("\nCzas rozpoczecia obliczen - %.2d:%.2d:%.2d\n", czas_pocz->tm_hour,

czas_pocz->tm_min, czas_pocz->tm_sec);

printf("\nLicze...\n");

wynik = RekurencyjnyFib(liczba);

printf("Fibonacci(%d) = %d \n", liczba, wynik);

printf("\n");

t2=time(NULL);

czas_koncowy=localtime(&t2);

printf("Czas zakonczenia obliczen - %.2d:%.2d:%.2d\n", czas_koncowy->tm_hour,

czas_koncowy->tm_min, czas_koncowy->tm_sec);

printf("\nCzas obliczen: %f sekund", difftime(t2,t1));

getche();

}

Jednakże dla dużych n stos programu nie wytrzyma tak dużej realizacji funkcji Fib (dla n powyżej 50). Zatem rekurencyjna implementacja funkcji Fibonacciego jest bardzo nieefektywna. Oznacza to, że program ma zbyt dużą złozoność pamięciową. Doskonale można to wyczytać z powyzszego drzewa wywołań dla n równego 6:

I jeszcze tabela efektywności rekurencyjnego wykonania tej funkcji:

n	Liczba dodawań	Liczba wywołań
6	12	25
10	88	177
15	986	1973
20	10945	21891
25	121392	242785
30	1346268	2692537

Bardziej efektywna jest jednak iteracyjna implementacja tej funkcji. Nie przepełniamy wtedy stosu programu i wykonujemy znacznie mniejszą liczbę przypisań wartości niż w implementacji rekurencyjnej. Oto przykład iteracyjnej implementacji tej funkcji:

long int Iteracyjny(int n)

{

register int i=2, last=0, tmp; long int current=1;

if (n<2) return n;

else {

for ( ; i<n;i++) {

tmp=current;

current+=last;

last=tmp;

}

return current;

}

}

I program obliczający n Fibonacciego tą właśnie metodą:

#include <stdio.h>

#include <time.h>

long int IteracyjnyFib(int n)

{

register int i=2, last=0, tmp; long int current =1;

if (n<2)

return n;

else {

for ( ; i<=n; i++) {

tmp = current;

current += last;

last = tmp;

}

return current;

}

}

main()

{

struct tm *czas_pocz, *czas_koncowy;

time_t t1,t2;

long liczba, wynik;

printf("Program obliczajacy n-ty wyraz ciagu Fibonacciego \n");

printf("\nPodaj liczbe n= ");

scanf("%d", &liczba);

t1=time(NULL);

czas_pocz=localtime(&t1);

printf("\nCzas rozpoczecia obliczen - %.2d:%.2d:%.2d\n", czas_pocz->tm_hour,

czas_pocz->tm_min, czas_pocz->tm_sec);

printf("\nLicze...\n");

wynik = IteracyjnyFib(liczba);

printf("Fibonacci(%d) = %d \n", liczba, wynik);

printf("\n");

t2=time(NULL);

czas_koncowy=localtime(&t2);

printf("Czas zakonczenia obliczen - %.2d:%.2d:%.2d\n", czas_koncowy->tm_hour,

czas_koncowy->tm_min, czas_koncowy->tm_sec);

printf("\nCzas obliczen: %f sekund", difftime(t2,t1));

getche();

}

Tabela ilustrująca efektywność znacznie ulegnie zmianie dla tej metody i dla n równego 6 liczba przypisań wyniesie 15, a nie 25. Z kolei dla 10 - 27, dla 15 - 42, dla 20 - 57, dla 25 - 72, dla 20 - 87. A teraz jeszcze jedna z pułapek rekurencji. Co się stanie jak wykonamy ten program i wprowadzimy n:

#include <stdio.h>

#include <conio.h>

int jakas_funkcja(int n){

printf("Wykonanie funkcji\n");

if (n==1)

return 1;

else

if ((n%2)==0) // czy n jest parzyste?

return jakas_funkcja(n-2)*n;

else

return jakas_funkcja(n-1)*n;

}

int main() {

int n;

printf("Podaj n\n");

scanf("%d",&n);

printf("jakas_funkcja(%d)= %d",n, jakas_funkcja(n));

getche();

return 0;

}

Program się zawiesi. Po przeanalizowaniu kodu można zobaczyc, dlaczego. Teraz natomiast nieco o idealnych algorytmach. Idealny algorytm to taki, który ma czytelny i zrozumiały kod, jest napisany w ogólnodostępnym języku programowania, jest efektywny obliczeniowo (szyblo liczy i nie wymaga dużej pamięci), oraz zawsze daje poprawne wyniki. Jeśli chodzi o kryteria to liczy się zatem prostota, czytelność kodu, długośc kodu, poprawność, czas realizacji (obliczeń) jak również zajęztość pamięci. Wyróżniamy częściową poprawnośc algorytmu i całkowitą poprawnośc algorytmu i teraz o tym kilka słów. Specyfikacją algorytmu nazywamy parę warunków (własności) o postaci <wp, wk>, gdzie wp to warunek początkowy, wk - warunek końcowy, oraz
. Algorytm A wykorzystujący strukturę danych S jest częściowo poprawny ze względu na specyfikację <wp, wk>, jeżeli dla wszystkich danych spełniających warunek poczatkowy i dla których algorytm zatrzyma się, uzyskane wyniki spełniają warunek końcowy. Z kolei mówimy, że algorytm A wykorzystujący strukturę danych S jest całkowicie poprawny ze względu na specyfikację <wp, wk>, jeżeli dla wszystkich danych w strukturze S spełniających rachunek początkowy wp, algorytm zatrzmuje się i daje wyniki spełniające warunek końcowy wk. Kolejny bardzo ciekawy temat to złozoność obliczeniowa algorytmów. Zlożoność obliczeniowa to miara służąca do porównywania efektywności algorytmów. Mamy dwa zasadnicze kryteria efektywności: czas i pamięć. Do oceny efektywności stosujemy jednostki logiczne wyrażające związek między rozmiarem danych n (przykładowo wielkośc pliku lub tablicy), a ilością czasu T potrzebną na ich przetworzenie. Stąd wyróżniamy zlozonośc czasową i pamięciową. Zlozoność pamięciowa wyrażana jest w skali zajętości pamięci (PAO, pamięci zewnętrznej), niezbednej dla realizacji algorytmu. Z kolei złozoność czasowa jest wyrażana w skali czasu wykonywania algorytmu (liczba kroków, czas rzeczywisty). Na ogół złozoność czasowa jest ważniejsza od złozoności pamięciowej. Wyróżniamy takie cztery czynniki wpływające na czas wykonywania programu. Są to: Rozmiar danych wejściowych algorytmu, Jakośc kodu wynikowego generowanego przez kompilator (język kodu źródłowego), architektura i szybkośc komputera na którym program jest wykonywany, oraz efektywność wykorzystywanego algorytmu (jego złożonośc czasowa). Złożoność czasowa algorytmu jest to liczba operacji podstawowych wykonanych przez algorytm w czasie jego realizacji, wyrażona jako funkcja rozmiaru danych. Złożonośc czasową algorytmu A jako funkcję rozmiaru danych n oznaczamy nastepująco: T(A,n) lub po prostu T(n). Do oszacowania czasu realizacji algorytmu nie powinno się używać zwykłych jednostek czasu. Zamiast tego powinny być stosowane jednostki logiczne, okreslające związek między rozmiarem danych wejściowych, a czasem potrzebnym na ich przetworzenie. Funkcje opisujące związek między T(n), a n mogą być bardzo złożone. W praktyce upraszczamy je pozostawiając takzwane składowe dominujące, czyli składowe mające największy wpływ na wartości T(n). Niech zależnośc czasu realizacji algorytmu od rozmiaru danych wejściowych opisuje funkcja:

. Na poczatek zobaczmy, jak będzie wyglądało porównanie szybkości wzrostu funkcji:

A teraz spójrzmy na szybkośc wzrostu poszczególnych składników funkcji:

Dla duzych wartości n składnikiem dominującym jest n do kwadratu, co oznacza, że funkcja rośnie, jak n do kwadratu, a pozostałe składniki mogą być pominięte (n - ilośc wykonywanych operacji). Teraz kilka słów o asymptotycznej złożoności obliczeniowej. Funkcja wyrażająca zależność między n a T jest zwykle bardzo skomplikowana, a jej dokładne obliczenie ma znaczenie jedynie w odniesieniu do specyficznych problemów. Przybliżoną miara efektywności najczęsciej strosowaną w praktyce jest asymptotyczna złozonośc obliczeniowa. Weźmy na przykład O - notację. Funkcja f(n) jest funkcja o złozoności O(g(n)), jeżeli istnieją takie liczby dodatnie c i
, że dla każdego
zachodzi:

. Zgodnie z tą definicją związek między funckjami f i g można wyrazić stwierdzając, że g(n) jest kresem górnym dla f(n). Istenieje jednak pewna uwaga, że definicja ta nie daje żadnych wskazówek co do tego, jak wyznaczyc stałe c i
(takich par może być wiele). Powyższą definicję natomiast możemy zinterpretować nastepujaco, że: O(g(n)) =

{ f(n): istnieją dodatnie liczby c i
takie, że dla każdego
zachodzi
}. Można to róznież zapisać tak:
.

Zilustrujmy graficznie O - notację:

Rozpatrzmy więc przykład. Niech zależnośc czasu realizacji algorytmu od rozmiaru danych wejściowych n opisuje funkcja
. Wówczas wykorzystując O - notację można zapisać, że:
. Zatem rząd badanej funkcji to będzie
. Tak określona złożonośc algorytmu nazywa się asymptotyczną złozonością czasową. W praktyce wykorzystuje się także pojęcia optymistycznej, pesymistycznej, oraz średniej złożoności czasowej algorytmu. O - notacja posiada kilka własności. Pierwsza z nich to przechodniość. Jeśli f(n) jest O (g(n)) i g(n) jest O(h(n)), to f(n) jest O(h(n)). Własnośc druga brzmi: jeśli f(n) jest O(h(n)) i g(n) jest O(h(n)), to f(n) + g(n) jest O(h(n)). Kolejna trzecia własność - funkcja
jest
. Kolejna - funkcja
jest
dla dowolnego nieujemnego j. Z powyższych czterech własności wynika, że dowolny wielomian jest O dla n podnesionego do najwyższej w nim potęgi, czyli
jest
. I nastepne własności. Teraz kolej na własnośc piątą - Jeśli f(n) = c g(n), to n) jest O(g(n)). Własność 6: funkcja
jest
dla dowolnych a i b większych niż 1. Własność kolejna (siódma):
jest
dla dowolnego dodatniego a. St ąd wynika wniosek, ze wszystkie funkcje logarytmiczne (niezależnie od podstawy logarytmu) są sobie równoważne w sensie O - notacji. No i ostatnie dwie własności. Oto pierwsza z nich (reguła sumy): Jeśli
są czasami wykonywania dwóch fragmentów algorytmu, to łączny czas wykonania obu fragmentów wynosi
. No i ostatnia z tych reguł zwana regułą iloczynu. Niech
są czasami wykonywania dwóch fragmentów algorytmu. Wówczas:
. Jedną z najważniejszych funkcji przy ocenianiu efektywności algorytmów jest funkcja logarytmiczna. Jeżeli można wykazać, że złożoność algorytmu jest rzędu logarytmicznego, algorytm można traktować jako bardzo dobry. Istnieje wiele funkcji lepszych w tym sensie niż logarytmiczna, jednak zaledwie kilka spośród nich jak na przykład O(l),
ma praktyczne znaczenie. O - notacja dotyczy kresu górnego funkcji. Istnieje symetryczna definicja kresu dolnego w postaci
- notacji. Na poczatek definicja. F(n) jest funkcją o złożoności
jeżeli istnieją takie liczby dodatnie c i
, że dla każdego
zachodzi
. Stąd wniosek, że funkcja ma złożoność
wtedy i tylko wtedy, gdy g(n) ma złożoność O(f(n)). Zinterpretować można to tak:
istnieją dodatnie liczby c i
takie, że dla każdego
zachodzi
. A piszemy:
, lub częściej
. I oto, jak przedstawia się ilustracja graficzna tej notacji:

No i ostatnia z notacji, czyli
notacja. F(n) jest funkcją o złożoności
jeżeli istnieją takie liczby dodatnie
, że dla każdego
zachodzi
. Stąd wniosek, że funkcja ma złożoność
wtedy i tylko wtedy, gdy f(n) ma złożoność O(g(n)) i f(n) ma złożoność
. Zinterpretować można to tak:
istnieją dodatnie liczby
takie, że dla każdego
zachodzi
. A piszemy:
, lub częściej
. I oto, jak przedstawia się ilustracja graficzna tej notacji:

Ta ostatnia z notacji jak widać byłaby najlepsza dlatego, że daje ona połączenie dwóch poprzednich i jest ona o tyle dokładna, że posługujemy się większą ilością stałych.A teraz nieco podsumowania. Podsumujmy najpierw notację asymptotyczną. Niech
.

Teraz porównajmy szybkość wzrotu funkcji. Mówimy, że Algorytm A ma złożoność czasową:

- Logarytmiczną, jeśli T(A, n) =

- Liniową, jeśli T(A, n) =

- Kwadratową, jeśli T(A, n) =

- Wielomianową, jeśli T(A, n) =

- Wykładniczą, jeśli T(A, n) =

Kolejną rzecza będzie porównanie rzedów funkcji. Istnieje pewien lemat o porównywaniu rzędów funkcji. Niech
. Wówczas:

1. Jeżeli
   , to f i g są tego samego rzędu

2. Jeżeli c = 0, to f = O(g), oraz
   

3. Jeżeli
   , to f ma rząd większy niż g, oraz g = O(f) i
   

Rozpatrzmy taki przykład. Niech f(n)=100n, g(n)=2n+100, h(n)=
. Stosując się do powyższego lematu mamy: f = O(n), f =
, g = O(n), ale także
,

. Teraz z kolei poruszymy temat, który brzmi: złożoność, a rozmiar i czas. Istotne będą dwie tabele. Pierwsza odpowiada na pytanie: Ile czasu potrzeba na rozwiązanie zadań o ustalonym rozmiarze i złożoności:

Druga z kolei odpowiada na pytanie, jaki jest maksymalny rozmiar problemu n, który można rozwiązać w ustalonym czasie znając złożonośc algorytmu.

Z tych tabel możemy wywnioskować, że szybkie wykonanie programu zależy od złożoności czasowej algorytmu, a nie od szybkości procesora. Na podstawie tego nasuwa się kolejne pytanie, czy szybkośc procesora może przezwyciężyć złożoność. Załóżmy, że mamy 5 algorytmów
rozwiązujących ten sam problem. Niech
oznacza maksymalny rozmiar problemu , który można rozwiązać na komputerze 1 przy pomocy algorytmu
w ustalonym czasie t. Poniżej znajduje się tabela, która zawiera odpowiedzi, jaki jest maksymalny rozmiar problemu, który można rozwiązać w tym samym czasie t na komputerze 2, który jest 10 razy szybszy:

Widać, że dla komputera 1:
, a dla komputera 2:
. My szukamy takiego x, że T(A, x) = t. I liczymy:
. I tak
po uprzednim zlogarytmowaniu. Stąd wniosek, że mimo, że komputer jest 10 razy szybszy, to wzrost problemu dokonuje się jedynie o 3,2. Jeżeli więc byśmy to przyspieszenie zwiększali, to niestety ten przyrost byłby coraz mniejszy. I tak to działa. Teraz nieco inne przedstawienie tego samego problemu w postaci tabeli przedstawiającej wpływ dzisięciokrotnego przyspieszenia komputera na wzrost rozmiaru zadania:

Widać więc, że z pogarszaniem się wskaźnika złożoności ten względny przyrost jest coraz mniejszy. Stąd wniosek, ze warto jest szukać takiego algorytmu, który będzie efektywniejszy niż szukanie szybszego komputera na ten sam algorytm. Teraz przytoczymy kilka przykładów odnoszących się właśnie do wyznaczania złożoności czasowej. Pierwszy z nich to pojedyncza petla wyznaczająca sumę elementów wektora:

for (i=sum=0;i<n;i++)

sum=sum+a[i];

Liczba przypisań (zliczamy instrukcje podstawienia) całej pętli wyniesie 2 + 2n (jest liniowa), natomiast złożoność czasowa wyniesie T(n) = O(n). Algorytm przedstawiony w tak prostej postaci zagwarantuje nam więc bardzo szybkie obliczenie. Nastepny przykład to pętla podwójna wyznaczająca sumę elementów tablicy. I tak:

for (i=0;i<n;i++){

for (j=1;sum=a[0];j<=i;j++)

sum=sum+a[j];

printf(„\n suma podtablicy %d”,sum);

}

Widzimy tutaj pętlę w pętli, a więc złożoność czasowa wyniesie już
w skutek czego liczba przypisań będzie w całej pętli bardziej złożona i wyniesie:

Nastepne zagadnienie dotyczy złożoności czasowej algorytmów rekurencyjnych. Kiedy algorytm zawiera rekurencyjne wywołanie samego siebie, jego czas działania można często opisać zależnością rek7urencyjną (rekurencją), wyrażającą czas dla problemu rozmiaru n za pomocą czasów dla podproblemów mniejszych rozmiarów. Możemy więc uzyć narzędzi matematycznych , aby rozwiązać rekurencję i w ten sposób otrzymać oszacowania czasu działania algorytmu. I teraz jakie mamy metody rozwiązywania rekurencji. Wyróżniamy cztery. Pierwsza z nich to metoda podstawiania, gdzie zgadujemy oszacowanie, a nastepnie wykorzystujemy indukcję matematyczną. Koleja to metoda iteracyjna - tutaj przekształcamy rekurencje na sumę (korzystamy z technik ograniczania sum). Trzecia to metoda drzewa rekursji uzupełniająca metodę podstawienia i czwarta ostatnia, to metoda rekurencji uniwersalnej, gdzie stosujemy oszacowanie na rekurencje mające postać: T(n) = a T(n/b) + f(n), gdzie a ≥ 1, b > 1, a f(n) jest daną funkcją. I teraz omówimy każdą z nich. Metoda podstawiania polega na odgadnięciu postaci rozwiązania, a nastepnie wykazaniu przez indukcję, że jest ono poprawne. Trzeba także znaleźć wartości odpowiednich stałych. Metoda ta jest bardzo skuteczna, ale może być stosowana jedynie w przypadkach, kiedy można przewidzieć postać rozwiązania. Zobaczmy na przykład. Przyjmijmy na początek pewne oznaczenia, że
to największa liczba calkowita x taka, że x < a. Z kolei
to najmniejsza liczba calkowita x taka, że x > a. I załóżmy, że mamy postac rekurencji:
. Wówczas dla tej rekurencji zachodzi, że T(1) = 1, T(2) = 4, T(3) = 5, T(4) = 6 … I tutaj możemy oszacować, że przewidywanym rozwiązaniem rekurencji będize taka funkcja: T(n) = O(n lg n), co znaczy, że
c n lg n. Teraz należy dowieść indukcyjnie, że to oszacowanie jest poprawne. I tak zakładamy, że dla
zachodzi:
. I tutaj zastosujemy nastepującą indukcję:

A zatem:
. I mamy rozwiązanie, że
jest poprawne dla
. Kolejna z metod to iteracyjna. Polega ona na rozwijaniu (iterowaniu) rekurencji i wyrażaniu jej jako sumy składników zależnych tylko od warunków brzegowych. Mogą tu być użyte techniki sumowania do oszacowania rozwiązania. Rozwinięcie rekurencji jest uproszczona wersją metody iteracyjnej. Polega na rozpisaniu równania rekurencyjnego dla kolejnych wartości n, dodaniu otrzymanych równań stronami, oraz zredukowaniu jednakowych wyrazów i przekształceniu otrzymanej zależności tak, aby uzyskać jawną zależnośc funkcji T(n) od n. Metoda ta jest skutecznajedynie w odniesieniu do niektórych postaci rekurencji. Zobaczmy na przykład. Mamy funkcję silnia zapisaną rekurencyjnie:

int Silnia(int n){

if (n==0)

return 1;

else return n*silnia(n-1);

}

Złożoność czasowa tej funkcji wyniesie
, gdzie ta jedynka to czas wykonania jednej instrukcji porównania wartości, czyli ogólnie
. Oto, jak się rozwiązuje ten problem tą metodą:

A teraz zobaczmy na inny przykład. Mamy następującą postać rekurencji już bez kodu: T(n) = 3T(n/4) + n. I teraz iterujemy: T(n) = n + 3T(n/4) = n + 3[n/4 + 3T(n/16)] = n + 3n/4 + 9T(n/16) = n + 3n/4 + 9[n/16 + 3T(n/16)] = n + 3n/4 + 9n/16 + 27T(n/16)] = … I iterujemy tak długo, aż osiągniemy warunek brzegowy, czyli ity składnik w ciągu, który wynosi
. Iterowanie kończymy, gdy
, czyli
.

---