quickSort occurs when
each time a segment is split, either the left or right resulting
segment is empty. In this case,
t(n) = cn + t(n-1) for
n > 1 and
t(1) = d, where
c and
d are constants. Using the substitution metod, we gett(n) = cn + t(n-1)
= c[n + (n-1)] + t(n-2)
= c[n + (n-1) + (n-2)] + t(n-3)
.
.
.
= c[n + (n-1) + (n-2) + ... + 2] + t(1)
= c[n(n+1)/2 - 1] + d
= Theta(n2)