CLRS 4.4-3 Height of recursion tree for T(N) = 4T(n/2 +2) + n

Question Detail: 

I'm having a hard time with the following question:

Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = 4T(n/2 + 2) + n$. Use the substitution method to verify your answer.

This is not homework, I'm just practicing myself for an upcoming exam.

The thing I'm having a hard time with is the $n/2 + 2$, what will the height be of this recursion tree?

I came up with the following formula to calculate the cost of each level after a lot of labor: $2^i n + 2^{i+2}(2^i -1)$ not 100% sure this is correct either.

Any help appreciated, really looking forward to the answer :D
I often make stupid mistakes and I just started doing algo's for my first time.

Asked By : Sam Stoelinga
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19343

Answered By : D.W.

I'll suggest two methods, but since this is your exercise, you'll have to work out some of the details. Important: study them both.


Method 1 (the dumb method)

We're going to use guess-and-check. In other words, we're going to guess a solution to the recurrence $T$, and then we'll check whether our guess is correct.

How do we come up with a reasonable guess? Well, we could try stuff blindly, but I have a better suggestion. The reason this recurrence is difficult is because of the nasty $+2$ in $T(n/2+2)$. So if that's inconvenient, let's throw it away: let's look at what happens with the related recurrence where that isn't present. In other words, define a new recurrence $U(\cdot)$ by

$$U(n) = 4 U(n/2) + n.$$

Now use your methods to find a solution to $U(n)$ (e.g., recursion tree, etc.). Finally, use that formulate for $U(n)$ and let's use that as our guess for $T(n)$: let's check whether it also provides an asympotically valid solution to $T(n)$. If it is, ta-da, you are done!

I call this a "dumb" method because, while it might happen to work on this example, there's no guarantee it will work in every situation. So that's why it is helpful to know a more powerful method:


Method 2 (transform of variables)

My suggestion is to first apply a change of variables to make that nasty $+2$ go away, then solve the transformed recurrence using standard methods you already know.

Here's an example. Suppose we define a new recurrence for $S(n)$ by making the definition $S(n) = T(n+3)$. (This corresponds to the change of variables $n \mapsto n+3$.) Can you derive a recurrence relation for $S(n)$? Sure, with some simple manipulation of the definitions of $S$ and $T$, you ought to be able to derive a recurrence of the form

$$S(n) = 4 S(\text{something}) + \text{stuff}.$$

In particular, I think you'll find that the $\text{something}$ has the form $n/2+\text{blah}$. So, go do it. Sit down with a pencil and work out the exact recurrence for $S(n)$ (fill in the $\text{something}$ and $\text{stuff}$ parts with their exact expressions).

Now if we were lucky, we'd get a recurrence of the form $S(n) = 4 S(n/2) + \text{stuff}$. That'd be lucky, because then you could use your standard methods to solve that kind of recurrence (now that the nasty $+2$ is gone). Unfortunately, when you work this out, you will discover that you were not lucky. The nasty $+2$ got replaced by some other $+\text{blah}$, which is still nasty (since $\text{blah}\ne 0$).

But don't give up. It turns out that $S(n)=T(n+3)$ was not lucky. So try a different definition. Try replacing the $3$ with some other number. If you play around with it a bit, I think you will discover that there is another number you can use instead of $3$ that will be lucky: it'll make the recurrence look like

$$S(n) = 4S(n/2) + \text{stuff},$$

and that's a recurrence you should know how to solve (e.g., recursion trees nad such). Once you find a solution for $S(n)$, you can plug back into the definition $S(n)=T(n+3)$ to get a solution for $T(n)$, and you're good.

This will work. It takes a little more work, but it is more general, so it is worth knowing. I suspect it is the method that your instructor wanted you to learn.

No comments

Powered by Blogger.