• Support PF! Buy your school textbooks, materials and every day products Here!

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

  • #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 im 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....
 
Last edited:

Answers and Replies

  • #2
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 im way off though...


2. Homework Equations
T(n)=T(n-1)+O(n lg n).
lg n = log_2 n


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


Now im 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?
 
Last edited:

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

Replies
3
Views
2K
  • Last Post
Replies
1
Views
8K
Replies
24
Views
4K
Replies
6
Views
1K
  • Last Post
Replies
5
Views
802
Replies
1
Views
436
Replies
12
Views
216
  • Last Post
Replies
4
Views
2K
Replies
8
Views
1K
Top