# Solving this recurrence relation

Hi all I'm preparing for a midterm and the following appeared as a practice problem that I'm not quite sure how to solve. It asks to find a tight bound on the recurrence using induction

$${\rm T}\left(n\right) ={\rm T}\left(\left\lfloor{n \over 2}\right\rfloor\right) +{\rm T}\left(\left\lfloor{n \over 4}\right\rfloor\right) +{\rm T}\left(\left\lfloor{n \over 8}\right\rfloor\right) +n$$

I'm aware a similar question has been asked here before, but that thread dates back to a year or so ago and I never really understood the rationale behind the answer given (see here: Need some help with this recurrence equation). My guess is that it is in $\Theta(n)$, but I'm not sure how to get a more precise relation than that. I've tried expanding out the recurrence a bit, but I'm not seeing any obvious pattern.

• Do you mean $$T(n)=T(\lfloor{\frac{n}{2}}\rfloor)+T(\lfloor{\frac{n}{4}}\rfloor)+T(\lfloor{ \frac{n}{8} }\rfloor)+n?$$ – Omnomnomnom Mar 17 '14 at 4:03
• Indeed I did. My apologies – user979616 Mar 17 '14 at 4:05
• While I'm at it (now I'm just being picky), rational is an adjective (unless you mean a number), rationale is the noun you're looking for. – Omnomnomnom Mar 17 '14 at 4:06
• haha thank you. I found the two answers given to this question came to the same conclusion, but were totally different in their approaches and I felt a tad mathematically complex for something which I wasn't expecting to be terribly difficult. – user979616 Mar 17 '14 at 4:14
• Neither of them used induction, either. Honestly, I'm not sure what exactly they're going for. – Omnomnomnom Mar 17 '14 at 4:20

The solution is cleary increasing. Use the change of variables $n = 2^k$ and $T(2^k) = a_k$, so that:

$$a_k = a_{k - 1} + a_{k - 2} + a_{k - 3} + 2^k$$

This is the same as:

$$a_{k + 3} = a_{k + 2} + a_{k + 1} + a_k + 8 \cdot 2^k$$

Define $A(z) = \sum_{k \ge 0} a_k z^k$, multiply the recurrence by $z^k$ and sum over $k \ge 0$ to get, after recognizing some sums:

$$\frac{A(z) - a_0 - a_1 z - a_2 z^2}{z^3} = \frac{A(z) - a_0 - a_1 z}{z^2} + \frac{A(z) - a_0}{z} + A(z) + 8 \cdot \frac{1}{1 - 2 z}$$

Set $a_0 = a_1 = a_2 = 1$ so that:

$$A(z) = \frac{1 - 2 z - 2^2 + 10 z^3}{(1 - 2 z) (1 - z - z^2 - z^3)}$$

By Descarte's rules of signs, $p(z) = 1 - z - z^2 - z^3$ has at most one positive zero, and we know $p(0) = 1$ and $p(1) = -2$ (the positive root is 0.543689, but in any case it is less than 1). Considering $p(-z) = 1 + z - z^2 + z^3$, again by the same rule there are at most 2 negative zeros. But we can write:

$$p(z) = 1 - \frac{z (z^3 - 1)}{z - 1}$$

For negative $z$, the second term is positive, there are no negative zeros.

A simple bound on the zeros of $a_0 + \dotsb + a_n z^n$ is that they are in the circle of radius $\rho$ around the origin, where:

$$\rho = \min\left\{ n \left\lvert \frac{a_0}{a_1} \right\rvert, \sqrt[n]{\left\lvert \frac{a_0}{a_n} \right\rvert} \right\}$$

This gives $\rho = 1$ in our case. By Bender's theorem (Bender, "Asymptotic Methods in Enumeration", SIAM Review 16:4 (oct 1974), pp 485-515), which states that if $A(z) = \sum_{n \ge 0} a_n z^n, B(z) = \sum_{n \ge 0} b_n z^n$, with convergence radii $\alpha \ge \beta > 0$, $C(z) = A(z) \cdot B(z) = \sum_{n \ge 0} c_n z^n$, with $\lim_{n \to \infty} \frac{b_{n - 1}}{b_n} = b$, $A(b) \ne 0$ then $c_n \sim A(b) b_n$.

The limit $b = 1/2$, so the theorem tells us that:

$$a_k \sim 8 \cdot 2^k$$

Translating back, $T(n) \sim 8 n$

Inductive step: assume $T(k) \leq Ck$ for all $k<n$. We then have \begin{align} T(n) &= T\left(\left\lfloor{n \over 2}\right\rfloor\right) +T\left(\left\lfloor{n \over 4}\right\rfloor\right) +T\left(\left\lfloor{n \over 8}\right\rfloor\right) +n\\ & \leq C\left(\left\lfloor{n \over 2}\right\rfloor\right) +C\left(\left\lfloor{n \over 4}\right\rfloor\right) +C\left(\left\lfloor{n \over 8}\right\rfloor\right) +n\\ & \leq C\left({n \over 2}\right) +C\left({n \over 4}\right) +C\left({n \over 8}\right) +n\\ &= \frac{7}{8}C\,n + n = \left(\frac{7}{8} C + 1\right)n \leq Cn \end{align} In order for this to work, we'd need $C \geq 8$. In fact, we can get it to work with $C = 8$. Just note (for the base case) that $$T(0) = 3T(0) + 0 \implies T(0) = 0$$ So that we have $T(0) \leq 8\cdot 0$. Great, there's our upper bound! That is, we have shown that $T(n) \leq 8n$, so that $$T(n) = O(n)$$ Now, we need to show that $T(n) \geq cn$ for some $c$. Clearly, though, $T(n) \geq n$.

• This makes so much more sense. Thank you. I think reading the previous post just confused me. – user979616 Mar 17 '14 at 4:39

Take k = max{8, T(1)} and you can easily show by induction that T(n) is no greater than kn. The lower bound is trivial.