How to get from a recurrence relation to a time order

Question

So, I've been looking into reccurence relations for quicksort, and I can follow how they get to the final recurrence relation, but then they jump to a time order. For example:

Worst case: T(n) = T(n-1) + cn

Then they jump to the time order of: O(n^2)

I dont follow how they got from the recurrence relation to the time order...

Answer 1

You can solve this recurrence in the following manner :-

T(n)=T(n-1)+cn =T(n-1)+O(n)
T(n)=T(n-2)+c(n-1)+cn       {bcoz T(n-1)=T(n-2)+c(n-1)}
T(n)=T(n-3)+c(n-2)+c(n-1)+cn    {bcoz  T(n-2)=T(n-3)+c(n-2)}
.       .       .
.       .       .
.       .       .
.       .       .
T(n)=T(0)+c(1+2+3....+n)
T(n)=T(0)+c(n(n+1)/2)
T(n)=T(0)+O(n^2)

Therefore it is come out of order of n^2.