- #1

- 13

- 0

## 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: