Fill This Form To Receive Instant Help
Fill This Form To Receive Instant Help
Homework answers / question archive / Use the substitution method to prove that the recurrence: T(n) = T(n-1) + theta(n) has the solution T(n) = theta(n2)
Use the substitution method to prove that the recurrence:
T(n) = T(n-1) + theta(n) has the solution T(n) = theta(n2). Please note that this question is in quick sort assignment.
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.
