3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Where did that formula come from? Looks like it came out of thin air. More generally, what do you understand? Do you understand how to build a recursion tree? If so, have you tried applying those methods to this problem? What did you get? What happens if you try to solve $U(n) = 4U(n/2) + n$? Can you find a solution to that? If you can, have you tried checking whether that solution also happens to solve the original recurrence (asymptotically)? The $n/2+2$ is indeed a pain, but the first thing I would try would be to analyze $U(n)$. $\endgroup$ – D.W. Dec 28 '13 at 20:00
  • $\begingroup$ Hi @D.W. yea I understand how to do it for U(n) = 4U(n/2) + n. The only thing that was giving me trouble is this n/2 + 2, all other exercises I did successfully. The formula came from the book. Just read your answer, thanks a lot. I think the substitution method is indeed the method I should learn for this question. I'm gonna work on it now :D $\endgroup$ – Sam Stoelinga Dec 29 '13 at 2:11
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I got $S(n) = T(n-4)$ , and then $S(n) = O(n^2)$ so $T(n) = S(n+4) = O((n+4)^2) = O(n^2)$ thats why the dummy method also worked. Were this correct conclusions? I wrote a total of 4 A4's for this question already lol. Fun question. Learned a lot. $T(n-4) = 4T((n-4)/2 + 2) + n-4 = 4T(n/2 -2 +2) + n-4$ $\endgroup$ – Sam Stoelinga Dec 29 '13 at 7:02
  • $\begingroup$ We get here T(n - 4) = 4T(n/2) + n-4, and if we write this in S(n) form, then the equation becomes, S(n) = 4S(n/2 + 4) + n - 4, so what I don't understand is how is the above equation simplified, to solve the recurrence. Please help $\endgroup$ – Debasish Mohapatra May 11 '17 at 3:38
  • $\begingroup$ @D.W. what you said will not lead to any change. I don't know how people upvoted your answer. $\endgroup$ – Mosab Shaheen Apr 7 at 19:04
  • $\begingroup$ @SamStoelinga how did you know that S(n)=O(n^2) check what Debasish said $\endgroup$ – Mosab Shaheen Apr 7 at 19:05
  • $\begingroup$ That's because what Sam Stoelinga wrote isn't correct (as Debasish Mohapatra correctly explains). You'll need to set $S(n) = T(n+c)$ for some constant $c$, and you'll need to choose $c$ appropriately to make things work. Contrary to what Sam Stoelinga wrote, $c=-4$ doesn't work, but there is another value of $c$ that does work. If you pick the right $c$ it will lead to a change that simplifies things. I'm going to let you discover what value does work, because it is a good exercise. $\endgroup$ – D.W. Apr 7 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.