Prove the following recurrence by induction
T(n) = 2T(n/2) + n lg n = Θ ( n lg^2 n ), T(1) = 1

This to me looks scary and I was wondering if anybody had a heads up on how to solve for this

Do you have any experience with the principle of mathematic induction? It would be easier to help if you showed us what you had so far.

What does mathematical induction have anything to do with this?

Anywho, this recurrence is actually not hard at all, it doesn't require any tricks and is pretty straightforward. It is solved by a method of backwards substitution - probably the most simplest way of solving recurrences. Search online for this method if you're not sure what it is. Some suggestions to make this thing easier:

1. Assume that n is a power of 2 and represent it as 2^k where k = log 2 (base 2 is assumed). Work with this representation instead. Substitute it everywhere, even into the n logn term. There is a theorem that states that even if n is not a power of 2 it will have the same growth as if it were.
2. Do the backwards substitution to see the pattern this thing is taking, you will be left with an easy finite series that you can solve.

I'll write this thing out in OpenOffice.org Math shortly (doing homework at the moment).

Edit: Here it is:




That's the exact growth. You may ignore the constant and the lesser terms, in which case it becomes the answer that you had.

This post has been edited by Neumann: 15 Sep, 2009 - 03:26 PM

Although I probably should have assumed inductive reasoning rather than proof by pmi.

I suppose you "could" take the:

Prove base case 1.
Prove for n+1
???
Profit??


method

This post has been edited by KYA: 15 Sep, 2009 - 07:30 PM

Yes, that's what a mathematical induction is. Now, I have approached this problem from a harder perspective - I am given a function. I have to find its complexity. In such case mathematical induction is completely useless. But I have obviously misread the problem, because it already gives us the answer, and simply wants to prove that it's true. In this case, we can use mathematical induction. First note that we're dealing with Big-Theta, in which case the problem usually requires us to:

1. Pull a constant c1 out of our ass.
2. Pull a constant c2 out of our ass.
3. Pull a constant x out of our ass.
4. Prove that:

That's all. Now, because I have already found the closed formula for this function, there's no need to pull anything, simply use it to get the constants. They are:

c1 = 1/2
c2 = 2
x = 2

Now all you need to do is prove the two inequalities with the base case being n = 2.

This post has been edited by Neumann: 15 Sep, 2009 - 08:42 PM