I am trying to solve this here recurrence : T(n)=T(n-1)+O(n lg n).
I am trying to do it by guessing the solution, and then use substitution to prove it right. I think that im way off though...
T(n)=T(n-1)+O(n lg n).
lg n = log_2 n
The Attempt at a Solution
Intuitively the "height" of the recursion will be h=n-2, i.e there will be n-1 levels. Level 0 has a cost of n lg n and Level n-1 will have cost T(1). If i sum the cost's, and try to bound by an arithmetic series i arrive at a guess of n^2.
Now, by substitution i guess that it will hold for some constant c >= (lg n+n-2)/2
Hmm... Thank's in advance for any help....