# 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?$$ Mar 17, 2014 at 4:03
• Indeed I did. My apologies Mar 17, 2014 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. Mar 17, 2014 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. Mar 17, 2014 at 4:14
• Neither of them used induction, either. Honestly, I'm not sure what exactly they're going for. Mar 17, 2014 at 4:20

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. Mar 17, 2014 at 4:39

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$$.

Apply this with $$A(z) = (1 - 2 z - 2^2 + 10 z^3) / (1 - z - z^2 - z^3)$$ and $$B(z) = (1 - 2 z)^{-1}$$. 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$$

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.