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