Solving recurence T(n)=T(n-1)+O(n lg n)

[kasper_2211]

Homework Statement

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 I am way off though...

Homework Equations

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...

 

[kasper_2211]

Here is a, maybe, better attempt at a solution.

1. Homework Statement
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 I am way off though...2. Homework Equations
T(n)=T(n-1)+O(n lg n).
lg n = log_2 n3. The Attempt at a Solution
First i try to 'unfold' the recursion,
T(n) = T(n-1) + c n lg n
= c n lg n + T(n-1)
=c n-1 lg n-1 + T(n-2)
=c n-1 lg n-1 + c n-2 lg n-2 + T(n-3)
= c n-1 lg n-1 + c n-2 lg n-2 + c n-3 lg n-3 + ... + T(1)

Since this is some decreasing series i try to bound it like so,
T(n) = c n lg n + c n-1 lg n-1 + c n-2 lg n-2 + c n-3 lg n-3 + ... + T(1) <= c n lg n + c n lg n + c n lg n + ... + T(1)

Now since there is approximately n terms this becomes,

T(n) <= c n^2 lg n

So my guess is that the solution is T(n) = O(n^2 lg n)
Does the above reasoning make any sense?

So guessing at O(n^2 lg n)

Assuming that T(1) = 1
base case 1 : 1 <= 1 lg 1 = 0 -> fails
base case 2 : T(1) + 2 lg 2 <= 4 lg 2 <=> 2 <= 4 -> OK
Now assume that for 2 <= k < n : T(k) <= c k^2 lg k

Induction, (d is supposed to be the constant hidden inside O(n lg n))
T(n) = T(n-1) + d n lg n
<= c (n-1)^2 lg (n-1) + d n lg n by I.H
<= c n^2 lg n + d n lg nNow I am a little stuck...I guess that somehow in the limit c n^2 lg n + d n lg n <= c n^2 lg n, but i don't think i can use that...Also, it looks almost correct but i need to get rid of the lower order term d n lg n. Is this possible?