Solving this recurrence relation

Question

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.

Answer 1

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$

Answer 2

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.

Answer 3

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