Page 32 - MATINF Nr. 7

32 C. B˘alc˘au

diferent , a absolut˘a a dimensiunilor lor este maxim˘a. Evident, |n + 1 − 2k| este maxim pentru
k ∈ {1, n}, deci
§
0, dac˘a n ∈ {0, 1},
+
N (n) =
+
N (n − 1) + n − 1, dac˘a n ≥ 2
+
(deoarece N (0) = 0). Aceast˘a situat , ie apare, de exemplu, atunci cˆand vectorul A este de la
ˆınceput sortat cresc˘ator (deoarece procedura PIVOT va fi apelat˘a succesiv pentru perechile de
indici (1, n), (2, n), . . . , (n − 1, n)). Avem

+
+
N (n) = N (n − 1) + n − 1
+
= N (n − 2) + (n − 2) + (n − 1)
. . .
+
= N (1) + 1 + 2 + . . . + (n − 2) + (n − 1),
deci
n(n − 1)
+
N (n) = , ∀ n ∈ N. (2)
2
Demonstr˘am c˘a
+
N(n) ≤ N (n), ∀ n ∈ N
prin induct , ie.

+
Pentru n ∈ {0, 1} avem N(n) = N (n) = 0.
Presupunem inegalitatea adev˘arat˘a pentru orice i ∈ {0, 1, . . . , n−1} s , i o demonstr˘am pentru
ˆ
n (n ≥ 2). Intr-adev˘ar, folosind relat , ia de recurent , ˘a (1), ipoteza de induct , ie pentru k − 1 s , i
n − k s , i relat , ia (2) avem

N(n) = N(k − 1) + N(n − k) + n − 1
+
+
≤ N (k − 1) + N (n − k) + n − 1
(k − 1)(k − 2) (n − k)(n − k − 1)
= + + n − 1
2 2
n(n − 1)
= − (k − 1)(n − k)
2
n(n − 1)
≤ .
2

Mai mult, egalitatea are loc dac˘a s , i numai dac˘a k ∈ {1, n} (la fiecare partit , ionare!).

n(n − 1)
+
Astfel Cazul 1) este cel mai defavorabil, avˆand num˘arul de comparat , ii N (n) = s , i,
2
2
prin urmare, complexitatea Θ(n ).
−
Cazul 2) Not˘am cu N (n) num˘arul de comparat , ii de chei efectuate de algoritm ˆın cazul
ˆın care la fiecare partit , ionare cele dou˘a partit , ii obt , inute sunt cˆat mai ,,echilibrate”, adic˘a
diferent , a absolut˘a a dimensiunilor lor este minim˘a. Evident, |n + 1 − 2k| este minim pentru
ž ¡
¤ª
§›
n + 1 n + 1
k ∈ , , deci
2 2

¡ ¤‹ › ž‹
 0, dac˘a n ∈ {0, 1},
−
N (n) = − n − 1 − n − 1 (3)
 N + N + n − 1, dac˘a n ≥ 2,
2 2