It easy to notice that T(1) = theta(1) (cost of ordering a one-element array). Then

T(n) = T(n-1) + theta(n)
= theta(n) + T(n-1)
= theta(n) + theta(n-1) + T(n-2)
...
= theta(n) + theta(n-1) + ... + theta(1)
n n
= SUM theta(i) = theta SUM( i )
i=1 i=1

= theta (n * (n + 1)/2) = theta (n^2)

Note, that this kind of behavior for quick sort happens if the input data are (almost) sorted. The behavior of quick sort is then no better than of insertion sort.