Need some help with this recurrence equation

Question

I'm self studying from a book I bought to learn more about algorithms and I've been trying most of the exercises in that book, so this is not a homework. Anyways, the relation I'm trying to solve is $$ T(n)=T(n/2)+T(n/4)+T(n/8)+n $$

I need to find a good asymptotic upper and lower bounds.

So, far what I've done is to transform the above considering $n=2^m$ then

$$ T(2^m)=T(2^{m-1})+T(2^{m-2})+T(2^{m-3})+2^m $$

then for $S(m)=T(2^m)$

$$ S(m)=S(m-1)+S(m-2)+S(m-3)+2^m $$

using the recursion tree with this later equation is a lot easier but I'm still not able to get to the solution.

Hope I'm on the right path :)

Answer 1

Technically the recurrence should use $\lfloor \frac{n}{2} \rfloor$ instead of $\frac{n}{2}$ (or ceiling, depending on the context), so that it is properly defined. It will look like this:

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

Typically, when analysing asymptotic behaviour, we can ignore the floors. (which gives $O(1)$ error) We extend $T(n)$ to $[0, \infty)$ with $T(n)=T(\lfloor n \rfloor)$. We now get back the equation you have:

$$T(n)=T\left(\frac{n}{2}\right)+T\left(\frac{n}{4}\right)+T\left(\frac{n}{8}\right)+n$$

Now, I shall show that $T(n)=8n+O(n^\theta)$, where $\theta \approx 0.87915$ is the only real root of $\left(\frac{1}{2}\right)^{\theta}+\left(\frac{1}{4}\right)^{\theta}+\left(\frac{1}{8}\right)^{\theta}-1=0$.

Indeed, if we subtract $8n$ from both sides of the above equation, we get:

$$(T(n)-8n)=(T\left(\frac{n}{2}\right)-\frac{8n}{2})+(T\left(\frac{n}{4}\right)-\frac{8n}{4})+(T\left(\frac{n}{8}\right)-\frac{8n}{8})$$

If we let $U(n)=T(n)-8n$, then

$$U(n)=U\left(\frac{n}{2}\right)+U\left(\frac{n}{4}\right)+U\left(\frac{n}{8}\right)$$

Suppose that for $1 \leq n \leq 8$, we have $an^{\theta} \leq U(n) \leq bn^{\theta}$, for some constants $a, b$. Indeed, we have

$$\min_{1 \leq i \leq 8, i \in \mathbb{Z}}{T(i)}-64 \leq U(n)=T(n)-8n \leq \max_{1 \leq i \leq 8, i \in \mathbb{Z}}{T(i)}-8$$

If we let $a=\min(0, \min_{1 \leq i \leq 8, i \in \mathbb{Z}}{T(i)}-64), b=\max(0, \max_{1 \leq i \leq 8, i \in \mathbb{Z}}{T(i)}-8)$, then $an^{\theta} \leq a \leq U(n) \leq b \leq bn^{\theta}$.

It is now easy to prove by induction on $k$ that $an^{\theta} \leq U(n) \leq bn^{\theta} \, \forall n \in [2^k, 2^{k+1}]$. When $k=0, 1, 2$, the statement is trivial. Suppose that it holds for $1 \leq k \leq i, i \geq 2$. Consider $n \in [2^{i+1}, 2^{i+2}]$, then

\begin{align} an^{\theta}& =a(\left(\frac{n}{2}\right)^{\theta}+\left(\frac{n}{4}\right)^{\theta}+\left(\frac{n}{8}\right)^{\theta}) \\ & \leq U(n) \\ & =U\left(\frac{n}{2}\right)+U\left(\frac{n}{4}\right)+U\left(\frac{n}{8}\right) \\ & \leq b(\left(\frac{n}{2}\right)^{\theta}+\left(\frac{n}{4}\right)^{\theta}+\left(\frac{n}{8}\right)^{\theta}) \\ &=bn^{\theta} \end{align}

We are thus done by induction.

Answer 2

We let the binary representation of $n$ be $$\sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ and assume for the base case that $T(0)=0$ and for the recursive step $$ T(n) = T(\lfloor n/2 \rfloor)+T(\lfloor n/4 \rfloor)+T(\lfloor n/8 \rfloor)+n.$$

Then the value of $T(n)$ for all $n$ is given by $$\sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1-\frac{1}{2}z -\frac{1}{4}z^2 -\frac{1}{8}z^3} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$ This formula is exact for all $n.$

Now let $\rho_{1,2,3}$ be the roots of $1-\frac{1}{2}z -\frac{1}{4}z^2 -\frac{1}{8}z^3 = 0,$ with $\rho_1$ the real root. Introduce $$ \rho =\sqrt[3]{17+3\sqrt{33}}$$ Then we have $$\rho_1 = \frac{2}{3} \rho - \frac{4}{3} \frac{1}{\rho} -\frac{2}{3} \quad\text{and}\quad \rho_{2,3} = -\frac{1}{3} \rho + \frac{2}{3} \frac{1}{\rho} -\frac{2}{3} \pm i \sqrt{3}\left(\frac{1}{3} \rho + \frac{2}{3} \frac{1}{\rho}\right).$$ This yields $$[z^j] \frac{1}{1-\frac{1}{2}z -\frac{1}{4}z^2 -\frac{1}{8}z^3}\\ = \frac{8\rho_1^{-j-1}}{(\rho_1-\rho_2)(\rho_1-\rho_3)}+ \frac{8\rho_2^{-j-1}}{(\rho_2-\rho_1)(\rho_2-\rho_3)}+ \frac{8\rho_3^{-j-1}}{(\rho_3-\rho_1)(\rho_3-\rho_2)}. $$ The numeric values of the inverses of the roots are $$\frac{1}{\rho_1} \sim 0.9196433771 \quad\text{and}\quad \frac{1}{\rho_{2,3}} \sim -0.2098216888 \mp 0.3031453647 i.$$

Note that $1/\rho_1$ is real and that $1/\rho_{2,3}$ has the following modulus: $$ \left|\frac{1}{\rho_{2,3}}\right| = 0.3686763530.$$ This implies that the contribution from $1/\rho_1$ dominates asymptotically. To see this, simply note that $$\frac{|(1/\rho_{2,3})^j|}{|(1/\rho_1)^j|} = \frac{|1/\rho_{2,3}|^j}{|1/\rho_1|^j} \rightarrow 0 \quad \text{as}\quad j \rightarrow \infty.$$

What we have done here is really nothing more than apply the known rule that the radius of convergence of a Taylor series centered at zero is the distance to the nearest singularity, with the dominant asymptotics of the coefficients being contributed by powers of the inverse of the modulus of that singularity.

We are now ready to check the bounds, restricting ourselves to the contribution from $1/\rho_1.$ The case of a lower bound occurs when $n$ consists of a single one, followed by zeros, giving

$$ T(n) \ge 2^{\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1-\frac{1}{2}z -\frac{1}{4}z^2 -\frac{1}{8}z^3} \\ \sim 2^{\lfloor \log_2 n \rfloor} \frac{8}{\rho_1 (\rho_1-\rho_2)(\rho_1-\rho_3)} \sum_{j=0}^{\lfloor \log_2 n \rfloor} \rho_1^{-j}$$ or $$\frac{8\times 2^{\lfloor \log_2 n \rfloor} }{\rho_1 (\rho_1-\rho_2)(\rho_1-\rho_3)} \frac{1-1/\rho_1^{\lfloor \log_2 n \rfloor+1}}{1-1/\rho_1}\\= \frac{8\times 2^{\lfloor \log_2 n \rfloor} (1-1/\rho_1^{\lfloor \log_2 n \rfloor+1}) } {(\rho_1-1) (\rho_1-\rho_2)(\rho_1-\rho_3)}.$$

Now let $$ P(n) = \frac{8\times 2^{\lfloor \log_2 n \rfloor}} {(\rho_1-\rho_2)(\rho_1-\rho_3)} \quad\text{and}\quad Q(n) = \frac{8\times (2/\rho_1)^{\lfloor \log_2 n \rfloor}} {(\rho_1-\rho_2)(\rho_1-\rho_3)},$$ so that the lower bound becomes $$\frac{P(n)}{\rho_1-1} - \frac{Q(n)}{\rho_1(\rho_1-1)}.$$

The case of the upper bound occurs when $n$ is string of one digits, giving $$T(n) \le \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1-\frac{1}{2}z -\frac{1}{4}z^2 -\frac{1}{8}z^3} \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k \\= \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1-\frac{1}{2}z -\frac{1}{4}z^2 -\frac{1}{8}z^3} (2^{\lfloor \log_2 n \rfloor+1} - 2^j)$$

The first part of the difference is twice the term we calculated for the lower bound. The second part is

$$- \frac{8}{\rho_1 (\rho_1-\rho_2)(\rho_1-\rho_3)} \sum_{j=0}^{\lfloor \log_2 n \rfloor} (2/\rho_1)^j = - \frac{8}{\rho_1 (\rho_1-\rho_2)(\rho_1-\rho_3)} \frac{(2/\rho_1)^{\lfloor \log_2 n \rfloor+1}-1}{2/\rho_1-1}$$ or $$- \frac{8\times (2/\rho_1)^{\lfloor \log_2 n \rfloor+1}-1} {(2-\rho_1)(\rho_1-\rho_2)(\rho_1-\rho_3)} = - \frac{2 Q(n)}{\rho_1(2-\rho_1)} + \frac{1}{(2-\rho_1)(\rho_1-\rho_2)(\rho_1-\rho_3)} $$

It follows that the upper bound is $$ 2\frac{P(n)}{\rho_1-1} - 2 Q(n) \left(\frac{1}{\rho_1(\rho_1-1)} + \frac{1}{\rho_1(2-\rho_1)}\right) + \frac{1}{(2-\rho_1)(\rho_1-\rho_2)(\rho_1-\rho_3)}.$$

Putting the upper and the lower bound together and observing that we have $$P(n) \in \Theta(n)\quad\text{and}\quad Q(n) \in \Theta\left((2/\rho_1)^{\lfloor \log_2 n \rfloor}\right) = \Theta(n/2^{\log_2\rho_1 \log_2 n}) = \Theta(n^{1-\log_2\rho_1})$$

so that $$T(n) \in \Theta(n)$$ and the next term in the asymptotic expansion is $\Theta(n^{1-\log_2\rho_1})$.

Taking certain liberties with the precise meaning of asymptotic expansions, we have $$ T(n) \sim n - n^{1 - \log_2 \left(\frac{2}{3}\sqrt[3]{17+3\sqrt{33}} - \frac{4}{3} \frac{1}{\sqrt[3]{17+3\sqrt{33}}} -\frac{2}{3}\right)}.$$ (The exact coefficients on these terms are calculated above.)