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 :DI often make stupid mistakes and I just started doing algo's for my first time.
CLRS 4.4-3 Height of recursion tree for T(N) = 4T(n/2 +2) + n
algorithm analysis;recursion
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.