CLRS 4.4-3 Height of recursion tree for T(N) = 4T(n/2 +2) + n
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.
Post a Comment