Analiza algoritmilor recursivi EXERCITII SI PROBLEME, Metoda iteratiei referat

Analiza algoritmilor recursivi

Am vazut in exemplul precedent cat de puternica si, in acelasi timp, cat de eleganta este recursivitatea in elaborarea unui algoritm. Nu vom face o introducere in recursivitate si nici o prezentare a metodelor de eliminare a ei. Cel mai important castig al exprimarii recursive este faptul ca ea este naturala si compacta, fara sa ascunda esenta algoritmului prin detaliile de implementare. Pe de alta parte, apelurile recursive trebuie folosite cu discernamant, deoarece solicita si ele resursele calculatorului (timp si memorie). Analiza unui algoritm recursiv implica rezolvarea unui sistem de recurente. Vom vedea in continuare cum pot fi rezolvate astfel de recurente. Incepem cu tehnica cea mai banala.

5.3.1 Metoda iteratiei

Cu putina experienta si intuitie, putem rezolva de multe ori astfel de recurente prin metoda iteratiei: se executa primii pasi, se intuieste forma generala, iar apoi se demonstreaza prin inductie matematica ca forma este corecta. Sa consideram de exemplu recurenta problemei turnurilor din Hanoi. Pentru un anumit n > 1 obtinem succesiv

Rezulta t(n) = 2ⁿ 1. Prin inductie matematica se demonstreaza acum cu usurinta ca aceasta forma generala este corecta.

5.3.2 Inductia constructiva

Inductia matematica este folosita de obicei ca tehnica de demonstrare a unei asertiuni deja enuntate. Vom vedea in aceasta sectiune ca inductia matematica poate fi utilizata cu succes si in descoperirea enuntului asertiunii. Aplicand aceasta tehnica, putem simultan sa demonstram o asertiune doar partial specificata si sa descoperim specificatiile care lipsesc si datorita carora asertiunea este corecta. Vom vedea ca aceasta tehnica a inductiei constructive este utila pentru rezolvarea anumitor recurente care apar in contextul analizei algoritmilor. Incepem cu un exemplu.

Fie functia f : N N, definita prin recurenta

Sa presupunem pentru moment ca nu stim ca f (n) = n(n 1)/2 si sa cautam o astfel de formula. Avem

si deci, f (n) I O(n²). Aceasta ne sugereaza sa formulam ipoteza inductiei specificate partial IISP(n) conform careia f este de forma f (n) = an² bn c. Aceasta ipoteza este partiala, in sensul ca a, b si c nu sunt inca cunoscute. Tehnica inductiei constructive consta in a demonstra prin inductie matematica aceasta ipoteza incompleta si a determina in acelasi timp valorile constantelor necunoscute a, b si c.

Presupunem ca IISP(n 1) este adevarata pentru un anumit n 1. Atunci,

f (n) = a(n 1)² b(n 1) c n = an² (1 b 2a)n (a b c)

Daca dorim sa aratam ca IISP(n) este adevarata, trebuie sa aratam ca f (n) = an² bn c. Prin identificarea coeficientilor puterilor lui n, obtinem ecuatiile 1 b 2a = b si a b c = c, cu solutia a = b = 1/2, c putand fi oarecare. Avem acum o ipoteza mai completa, pe care o numim tot IISP(n): f (n) = n²/2 n/2 c. Am aratat ca, daca IISP(n 1) este adevarata pentru un anumit n 1, atunci este adevarata si IISP(n). Ramane sa aratam ca este adevarata si IISP(0). Trebuie sa aratam ca f (0) = a 0 b 0 c = c. Stim ca f (0) = 0, deci IISP(0) este adevarata pentru c = 0. In concluzie, am demonstrat ca f (n) = n²/2 n/2 pentru orice n.

5.3.3 Recurente liniare omogene

Exista, din fericire, si tehnici care pot fi folosite aproape automat pentru a rezolva anumite clase de recurente. Vom incepe prin a considera ecuatii recurente liniare omogene, adica de forma

a₀t_n a₁t_n-1 ¼ a_kt_n-k = 0 ( )

unde t_i sunt valorile pe care le cautam, iar coeficientii a_i sunt constante.

Conform intuitiei, vom cauta solutii de forma

t_n = xⁿ

unde x este o constanta (deocamdata necunoscuta). Incercam aceasta solutie in ( ) si obtinem

a₀xⁿ a₁x^n-1 a_kx^n-k = 0

Solutiile acestei ecuatii sunt fie solutia triviala x = 0, care nu ne intereseaza, fie solutiile ecuatiei

a₀x^k a₁x^k-1 a_k = 0

care este ecuatia caracteristica a recurentei ( ).

Presupunand deocamdata ca cele k radacini r₁, r₂, , r_k ale acestei ecuatii caracteristice sunt distincte, orice combinatie liniara

este o solutie a recurentei ( ), unde constantele c₁, c₂, , c_k sunt determinate de conditiile initiale. Este remarcabil ca ( ) are numai solutii de aceasta forma.

Sa exemplificam prin recurenta care defineste sirul lui Fibonacci (din Sectiunea 1.6.4):

t_n = t_n-1 t_n-2 n 2

iar t₀ = 0, t₁ = 1. Putem sa rescriem aceasta recurenta sub forma

t_n t_n-1 t_n-2 = 0

care are ecuatia caracteristica

x² x 1 = 0

cu radacinile r_1,2 = (1
)/2. Solutia generala are forma

Impunand conditiile initiale, obtinem

c₁ c₂ = 0 n = 0
r₁c₁ r₂c₂ = 1 n = 1

de unde determinam

c_1,2 =

Deci,
. Observam ca r₁ = f = (1
)/2, r₂ = -f^-1 si obtinem

(fⁿ (-f)^-n)

care este cunoscuta relatie a lui de Moivre, descoperita la inceputul secolului XVI. Nu prezinta nici o dificultate sa aratam acum ca timpul pentru algoritmul fib1 (din Sectiunea 1.6.4) este in Q(fⁿ).

Ce facem insa atunci cand radacinile ecuatiei caracteristice nu sunt distincte? Se poate arata ca, daca r este o radacina de multiplicitate m a ecuatiei caracteristice, atunci t_n = rⁿ, t_n = nrⁿ, t_n = n²rⁿ, , t_n = n^m-1rⁿ sunt solutii pentru ( ). Solutia generala pentru o astfel de recurenta este atunci o combinatie liniara a acestor termeni si a termenilor proveniti de la celelalte radacini ale ecuatiei caracteristice. Din nou, sunt de determinat exact k constante din conditiile initiale.

Vom da din nou un exemplu. Fie recurenta

t_n = 5t_n-1 8t_n-2 4t_n-3 n 3

iar t₀ = 0, t₁ = 1, t₂ = 2. Ecuatia caracteristica are radacinile 1 (de multiplicitate 1) si 2 (de multiplicitate 2). Solutia generala este:

t_n = c₁1ⁿ c₂2ⁿ c₃n2ⁿ

Din conditiile initiale, obtinem c₁ = 2, c₂ = 2, c₃ = 1/2.

5.3.4 Recurente liniare neomogene

Consideram acum recurente de urmatoarea forma mai generala

a₀t_n a₁t_n-1 a_kt_n-k = bⁿp(n) ( )

unde b este o constanta, iar p(n) este un polinom in n de grad d. Ideea generala este ca, prin manipulari convenabile, sa reducem un astfel de caz la o forma omogena.

De exemplu, o astfel de recurenta poate fi:

t_n 2t_n-1 = 3ⁿ

In acest caz, b = 3 si p(n) = 1, un polinom de grad 0. O simpla manipulare ne permite sa reducem acest exemplu la forma ( ). Inmultim recurenta cu 3, obtinand

3t_n 6t_n-1 = 3ⁿ⁺¹

Inlocuind pe n cu n 1 in recurenta initiala, avem

t_n+1 2t_n = 3ⁿ⁺¹

In fine, scadem aceste doua ecuatii

t_n+1 5t_n 6t_n-1 = 0

Am obtinut o recurenta omogena pe care o putem rezolva ca in sectiunea precedenta. Ecuatia caracteristica este:

x² 5x 6 = 0

adica (x 2)(x 3) = 0.

Intuitiv, observam ca factorul (x 2) corespunde partii stangi a recurentei initiale, in timp ce factorul (x 3) a aparut ca rezultat al manipularilor efectuate, pentru a scapa de parte dreapta.

Generalizand acest procedeu, se poate arata ca, pentru a rezolva ( ), este suficient sa luam urmatoarea ecuatie caracteristica:

(a₀x^k a₁x^k-1 ¼ a_k)(x b)^d+1 = 0

Odata ce s-a obtinut aceasta ecuatie, se procedeaza ca in cazul omogen.

Vom rezolva acum recurenta corespunzatoare problemei turnurilor din Hanoi:

t_n = 2t_n-1 1 n 1

iar t₀ = 0. Rescriem recurenta astfel

t_n 2t_n-1 = 1

care este de forma ( ) cu b = 1 si p(n) = 1, un polinom de grad 0. Ecuatia caracteristica este atunci (x 2)(x 1) = 0, cu solutiile 1 si 2. Solutia generala a recurentei este:

t_n = c₁1ⁿ c₂2ⁿ

Avem nevoie de doua conditii initiale. Stim ca t₀ = 0; pentru a gasi cea de-a doua conditie calculam

t₁ = 2t₀ 1

Din conditiile initiale, obtinem

t_n = 2ⁿ 1

Daca ne intereseaza doar ordinul lui t_n, nu este necesar sa calculam efectiv constantele in solutia generala. Daca stim ca t_n = c₁1ⁿ c₂2ⁿ, rezulta t_n I O(2ⁿ). Din faptul ca numarul de mutari a unor discuri nu poate fi negativ sau constant, deoarece avem in mod evident t_n n, deducem ca c₂ > 0. Avem atunci t_n I W(2ⁿ) si deci, t_n I Q(2ⁿ). Putem obtine chiar ceva mai mult. Substituind solutia generala inapoi in recurenta initiala, gasim

1 = t_n 2t_n-1 = c₁ c₂2ⁿ 2(c₁ c₂2^n-1) = c₁

Indiferent de conditia initiala, c₁ este deci 1.

5.3.5 Schimbarea variabilei

Uneori, printr-o schimbare de variabila, putem rezolva recurente mult mai complicate. In exemplele care urmeaza, vom nota cu T(n) termenul general al recurentei si cu t_k termenul noii recurente obtinute printr-o schimbare de variabila. Presupunem pentru inceput ca n este o putere a lui 2.

Un prim exemplu este recurenta

T(n) = 4T(n/2) n n > 1

in care inlocuim pe n cu 2^k, notam t_k = T(2^k) = T(n) si obtinem

t_k = 4t_k-1 2^k

Ecuatia caracteristica a acestei recurente liniare este

(x 4)(x 2) = 0

si deci, t_k = c₁4^k c₂2^k. Inlocuim la loc pe k cu lg n

T(n) = c₁n² c₂n

Rezulta

T(n) I O(n² | n este o putere a lui 2)

Un al doilea exemplu il reprezinta ecuatia

T(n) = 4T(n/2) n² n > 1

Procedand la fel, ajungem la recurenta

t_k = 4t_k-1 4^k

cu ecuatia caracteristica

(x 4)² = 0

si solutia generala t_k = c₁4² c₂k4². Atunci,

T(n) = c₁n² c₂n²lg n

si obtinem

T(n) I O(n²log n | n este o putere a lui 2)

In fine, sa consideram si exemplul

T(n) = 3T(n/2) cn n > 1

c fiind o constanta. Obtinem succesiv

T(2^k) = 3T(2^k-1) c2^k

t_k = 3t_k-1 c2^k

cu ecuatia caracteristica

(x 3)(x 2) = 0

t_k = c₁3^k c₂2^k

T(n) = c₁3^{lg n} c₂n

si, deoarece

a^{lg b} = b^{lg a}

obtinem

T(n) = c₁n^{lg 3} c₂n

deci,

T(n) I O(n^{lg 3} | n este o putere a lui 2)

In toate aceste exemple am folosit notatia asimptotica conditionata. Pentru a arata ca rezultatele obtinute sunt adevarate pentru orice n, este suficient sa adaugam conditia ca T(n) sa fie eventual nedescrescatoare. Aceasta, datorita Proprietatii 5.1 si a faptului ca functiile n², n log n si n^{lg 3} sunt netede.

Putem enunta acum o proprietate care este utila ca reteta pentru analiza algoritmilor cu recursivitati de forma celor din exemplele precedente. Proprietatea, a carei demonstrare o lasam ca exercitiu, ne va fi foarte utila la analiza algoritmilor divide et impera din Capitolul 7.

Proprietatea 5.2 Fie T : N R⁺ o functie eventual nedescrescatoare

T(n) = aT(n/b) cn^k n > n₀

unde: n₀ 1, b 2 si k 0 sunt intregi; a si c sunt numere reale pozitive; n/n₀ este o putere a lui b. Atunci avem

5.4 Exercitii

5.1 Care din urmatoarele afirmatii sunt adevarate?

i) n² I O(n³)

ii) n³ I O(n²)

iii) 2ⁿ⁺¹ I O(2ⁿ)

iv) (n 1)! I O(n!)

v) pentru orice functie f : N R , f I O(n) T [ f ² I O(n²)]

vi) pentru orice functie f : N R , f I O(n) T [2 ^f I O(2ⁿ)]

5.2 Presupunand ca f este strict pozitiva pe N, demonstrati ca definitia lui O( f ) este echivalenta cu urmatoarea definitie:

O( f ) =

5.3 Demonstrati ca relatia "I O" este tranzitiva: daca f I O(g) si g I O(h), atunci f I O(h). Deduceti de aici ca daca g I O(h), atunci O(g) O(h).

5.4 Pentru oricare doua functii f, g : N R , demonstrati ca:

i) O( f ) = O(g) f I O(g) si g I O( f )

ii) O( f ) O(g) f I O(g) si g O( f )

5.5 Gasiti doua functii f, g : N R , astfel incat f O(g) si g O( f ).

Indicatie: f (n) = n, g(n) = n^{1+sin n}

5.6 Pentru oricare doua functii f, g : N R definim urmatoarea relatie binara: f g daca O( f ) O(g). Demonstrati ca relatia " " este o relatie de ordine partiala in multimea functiilor definite pe N si cu valori in R .

Indicatie: Trebuie aratat ca relatia este partiala, reflexiva, tranzitiva si antisimetrica. Tineti cont de Exercitiul 5.5.

5.7 Pentru oricare doua functii f, g : N R demonstrati ca

O( f g) = O(max( f, g))

unde suma si maximul se iau punctual.

5.8 Fie f (n) = a_mn^m . a₁n a₀ un polinom de grad m, cu a_m > 0. Aratati ca f I O(n^m).

5.9 O(n²) = O(n³ (n² n³)) = O(max(n³, n² n³)) = O(n³)

Unde este eroarea?

5.10 Gasiti eroarea in urmatorul lant de relatii:

5.11 Fie f , g : N R⁺. Demonstrati ca:

Observatie: Implicatiile inverse nu sunt in general adevarate, deoarece se poate intampla ca limitele sa nu existe.

5.12 Folosind regula lui l'Hôspital si Exercitiile 5.4, 5.11, aratati ca

log n I O(
), dar
O(log n)

Indicatie: Prelungim domeniile functiilor pe R⁺, pe care sunt derivabile si aplicam regula lui l'Hôspital pentru log n/
.

5.13 Pentru oricare f, g : N R , demonstrati ca:

f I O(g) g I W( f )

5.14 Aratati ca f I Q(g) daca si numai daca

( c, d I R⁺) ( n₀ I N) ( n n₀) [cg(n) f (n) dg(n)]

5.15 Demonstrati ca urmatoarele propozitii sunt echivalente, pentru oricare doua functii f, g : N R .

i) O( f ) = O(g)

ii) Q( f ) = Q(g)

iii) f I Q(g)

5.16 Continuand Exercitiul 5.11, aratati ca pentru oricare doua functii f, g : N R⁺ avem:

i)
I R⁺ T f I Q(g)

ii)
= 0 T f I O(g) dar f Q(g)

iii)
= T f I W(g) dar f Q(g)

5.17 Demonstrati urmatoarele afirmatii:

i) log_an I Q(log_bn) pentru oricare a, b > 1

iv) log n! I Q(n log n)

Indicatie: La punctul iii) se tine cont de relatia:

= ln n g 1/2n 1/12n²

unde g = 0,5772 este constanta lui Euler.

La punctul iv), din n! < nⁿ, rezulta log n! I O(n log n). Sa aratam acum, ca log n! I W(n log n). Pentru 0 i n 1 este adevarata relatia

(n i)(i 1) n

Deoarece

(n )² = (n×1) ((n ) 2) ((n 2) 3) (2 (n 1)) (1 n) nⁿ

rezulta 2 log n! n log n si deci log n! I W(n log n).

Punctul iv) se poate demonstra si altfel, considerand aproximarea lui Stirling:

unde e = 1,71828 .

5.18 Aratati ca timpul de executie al unui algoritm este in Q(g), g : N R , daca si numai daca: timpul este in O(g) pentru cazul cel mai nefavorabil si in W(g) pentru cazul cel mai favorabil.

5.19 Pentru oricare doua functii f, g : N R demonstrati ca

Q( f ) Q(g) = Q( f g) = Q(max( f, g)) = max(Q( f ), Q(g))

unde suma si maximul se iau punctual.

5.20 Demonstrati Proprietatea 5.1. Aratati pe baza unor contraexemple ca cele doua conditii "t(n) este eventual nedescrescatoare" si "f (bn) I O( f (n))" sunt necesare.

5.21 Analizati eficienta urmatorilor patru algoritmi:

for i 1 to n do for i 1 to n do
for j 1 to 5 do for j 1 to i 1 do

for i 1 to n do for i 1 to n do
for j 1 to 6 do for j 1 to i do
for k 1 to n do for k 1 to n do

5.22 Construiti un algoritm cu timpul in Q(n log n).

5.23 Fie urmatorul algoritm

k 0
for i 1 to n do
for j 1 to T[i] do
k k T[ j]

unde T este un tablou de n intregi nenegativi. In ce ordin este timpul de executie al algoritmului?

Solutie: Fie s suma elementelor lui T. Daca alegem ca barometru instructiunea "k k T[ j]", calculam ca ea se executa de s ori. Deci, am putea deduce ca timpul este in ordinul exact al lui s. Un exemplu simplu ne va convinge ca am gresit. Presupunem ca T[i] = 1, atunci cand i este un patrat perfect, si T[i] = 0, in rest. In acest caz, s =
. Totusi, algoritmul necesita timp in ordinul lui W(n), deoarece fiecare element al lui T este considerat cel putin o data. Nu am tinut cont de urmatoarea regula simpla: putem neglija timpul necesar initializarii si controlului unei bucle, dar cu conditia sa includem "ceva" de fiecare data cand se executa bucla.

Iata acum analiza detailata a algoritmului. Fie a timpul necesar pentru o executare a buclei interioare, inclusiv partea de control. Executarea completa a buclei interioare, pentru un i dat, necesita b aT[i] unitati de timp, unde constanta b reprezinta timpul pentru initializarea buclei. Acest timp nu este zero, cand T[i] = 0. Timpul pentru o executare a buclei exterioare este c b aT[i], c fiind o noua constanta. In fine, intregul algoritm necesita
unitati de timp, unde d este o alta constanta. Simplificand, obtinem (c b)n as d. Timpul t(n, s) depinde deci de doi parametri independenti n si s. Avem: t I Q(n s) sau, tinand cont de Exercitiul 5.19, t I Q(max(n, s)).

5.24 Pentru un tablou T[1 .. n], fie urmatorul algoritm de sortare:

for i n downto 1 do
for j 2 to i do
if T[ j 1] > T[ j] then interschimba T[ j 1] si T[ j]

Aceasta tehnica de sortare se numeste metoda bulelor (bubble sort).

i) Analizati eficienta algoritmului, luand ca barometru testul din bucla interioara.

ii) Modificati algoritmul, astfel incat, daca pentru un anumit i nu are loc nici o interschimbare, atunci algoritmul se opreste. Analizati eficienta noului algoritm.

5.25 Fie urmatorul algoritm

for i 0 to n do
j i
while j 0 do j j div 2

Gasiti ordinul exact al timpului de executie.

5.26 Demonstrati ca pentru oricare intregi pozitivi n si d

Solutie:

Mai ramane sa aratati ca

5.27 Analizati algoritmii percolate si sift-down pentru cel mai nefavorabil caz, presupunand ca opereaza asupra unui heap cu n elemente.

Indicatie: In cazul cel mai nefavorabil, algoritmii percolate si sift-down necesita un timp in ordinul exact al inaltimii arborelui complet care reprezinta heap-ul, adica in Q( lg n ) = Q(log n).

5.28 Analizati algoritmul slow-make-heap pentru cel mai nefavorabil caz.

Solutie: Pentru slow-make-heap, cazul cel mai nefavorabil este atunci cand, initial, T este ordonat crescator. La pasul i, se apeleaza percolate(T[1 .. i], i), care efectueaza lg i comparatii intre elemente ale lui T. Numarul total de comparatii este atunci

C(n) (n 1) lg n I O(n log n)

Pe de alta parte, avem

In Exercitiul 5.17 am aratat ca lg n! I W(n log n). Rezulta C(n) I W(n log n) si timpul este deci in Q(n log n).

5.29 Aratati ca, pentru cel mai nefavorabil caz, timpul de executie al algoritmului heapsort este si in W(n log n), deci in Q(n log n).

5.30 Demonstrati ca, pentru cel mai nefavorabil caz, orice algoritm de sortare prin comparatie necesita un timp in W(n log n). In particular, obtinem astfel, pe alta cale, rezultatul din Exercitiul 5.29.

Solutie: Orice sortare prin comparatie poate fi interpretata ca o parcurgere a unui arbore binar de decizie, prin care se stabileste ordinea relativa a elementelor de sortat. Intr-un arbore binar de decizie, fiecare varf neterminal semnifica o comparatie intre doua elemente ale tabloului T si fiecare varf terminal reprezinta o permutare a elementelor lui T. Executarea unui algoritm de sortare corespunde parcurgerii unui drum de la radacina arborelui de decizie catre un varf terminal. La fiecare varf neterminal se efectueaza o comparatie intre doua elemente T[i] si T[ j]: daca T[i] T[ j] se continua cu comparatiile din subarborele stang, iar in caz contrar cu cele din subarborele drept. Cand se ajunge la un varf terminal, inseamna ca algoritmul de sortare a reusit sa stabileasca ordinea elementelor din T.

Fiecare din cele n! permutari a celor n elemente trebuie sa apara ca varf terminal in arborele de decizie. Vom lua ca barometru comparatia intre doua elemente ale tabloului T. Inaltimea h a arborelui de decizie corespunde numarului de comparatii pentru cel mai nefavorabil caz. Deoarece cautam limita inferioara a timpului, ne intereseaza doar algoritmii cei mai performanti de sortare, deci putem presupune ca numarul de varfuri este minim, adica n!. Avem: n! 2^h (demonstrati acest lucru!), adica h lg n!. Considerand si relatia log n! I W(n log n) (vezi Exercitiul 5.17), rezulta ca timpul de executie pentru orice algoritm de sortare prin comparatie este, in cazul cel mai nefavorabil, in W(n log n).

5.31 Analizati algoritmul heapsort pentru cel mai favorabil caz. Care este cel mai favorabil caz?

5.32 Analizati algoritmii fib2 si fib3 din Sectiunea 1.6.4.

Solutie:

i) Se deduce imediat ca timpul pentru fib2 este in Q(n).

ii) Pentru a analiza algoritmul fib3, luam ca barometru instructiunile din bucla while. Fie n_t valoarea lui n la sfarsitul executarii celei de-a t-a bucle. In particular, n₁ = n/2 . Daca 2 t m, atunci

n_t = n_t-1/2 n_t-1/2

Deci,

n_t n_t-1/2 . n/2^t

Fie m = 1 lg n . Deducem:

n_m n/2^m < 1

Dar, n_m I N, si deci, n_m = 0, care este conditia de iesire din bucla. Cu alte cuvinte, bucla este executata de cel mult m ori, timpul lui fib3 fiind in O(log n). Aratati ca timpul este de fapt in Q(log n).

La analiza acestor doi algoritmi, am presupus implicit ca operatiile efectuate sunt independente de marimea operanzilor. Astfel, timpul necesar adunarii a doua numere este independent de marimea numerelor si este marginit superior de o constanta. Daca nu mai consideram aceasta ipoteza, atunci analiza se complica.

5.33 Rezolvati recurenta t_n 3t_n-1 4t_n-2 = 0, unde n 2, iar t₀ = 0, t₁ = 1.

5.34 Care este ordinul timpului de executie pentru un algoritm recursiv cu recurenta t_n = 2t_n-1 n.

Indicatie: Se ajunge la ecuatia caracteristica (x 2)(x 1)² = 0, iar solutia generala este t_n = c₁2ⁿ c₂1ⁿ c₃n1ⁿ. Rezulta t I O(2ⁿ).

Substituind solutia generala inapoi in recurenta, obtinem ca, indiferent de conditia initiala, c₂ = 2 si c₃ = 1. Atunci, toate solutiile interesante ale recurentei trebuie sa aiba c₁ > 0 si ele sunt toate in W(2ⁿ), deci in Q(2ⁿ).

5.35 Scrieti o varianta recursiva a algoritmului de sortare prin insertie si determinati ordinul timpului de executie pentru cel mai nefavorabil caz.

Indicatie: Pentru a sorta T[1 .. n], sortam recursiv T[1 .. n 1] si inseram T[n] in tabloul sortat T[1 .. n 1].

5.36 Determinati prin schimbare de variabila ordinul timpului de executie pentru un algoritm cu recurenta T(n) = 2T(n/2) n lg n, unde n > 1 este o putere a lui 2.

Indicatie: T(n) I O(n log²n | n este o putere a lui 2)

5.37 Demonstrati Proprietatea 5.2, folosind tehnica schimbarii de variabila.