How to find a function that is the upper bound of this sum?

Question

The Problem Consider the recurrence $ T(n) = \begin{cases} c & \text{if $n$ is 1} \\ T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4)\rfloor) + 4n, & \text{if $n$ is > 1} \end{cases}$

A. Express the cost of all levels of the recursion tree as a sum over the cost of each level of the recursion tree
B. Give a function $g(n)$ and show that it is an upper bound on the sum

My Work
I was able to do part A. I drew the first six levels of the recursion tree and expressed the expressed the cost of all levels as $\sum_{i=0}^{log_2n} \frac{4n}{2^i}f(i+2) $ where $f(n)$ is the $n$^th term in the Fibonacci sequence(0, 1, 1, 2, 3, 5, 8)

How would I come up with a function that would be an upper bound of this sum?

Answer 1

Suppose we start by solving the following recurrence: $$T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + 4n$$ where $T(1) = c$ and $T(0) = 0.$

Now let $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ be the binary representation of $n.$ We unroll the recursion to obtain an exact formula for $n\ge 2$ $$T(n) = c [z^{\lfloor \log_2 n \rfloor}] \frac{1}{1-z-z^2} + 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} [z^j] \frac{1}{1-z-z^2} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}.$$

We recognize the generating function of the Fibonacci numbers, so the formula becomes $$T(n) = c F_{\lfloor \log_2 n \rfloor +1} + 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}.$$

We now compute lower and upper bounds which are actually attained and cannot be improved upon. For the lower bound consider a one digit followed by a string of zeroes, to give

$$T(n) \ge c F_{\lfloor \log_2 n \rfloor +1} + 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{\lfloor \log_2 n \rfloor-j} \\ = c F_{\lfloor \log_2 n \rfloor +1} + 8 \times 2^{\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{-j-1}.$$

Now since $$|\varphi|=\left|\frac{1+\sqrt{5}}{2}\right|<2$$ the sum term converges to a number, we have $$\frac{1}{2} \le \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{-j-1} \lt \sum_{j=0}^{\infty} F_{j+1} 2^{-j-1} = 2.$$

For an upper bound consider a string of one digits to get

$$T(n) \le c F_{\lfloor \log_2 n \rfloor +1} + 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^{k-j} \\ = c F_{\lfloor \log_2 n \rfloor +1} + 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} (2^{\lfloor \log_2 n \rfloor+1-j} - 1) \\ = c F_{\lfloor \log_2 n \rfloor +1} - 4 (F_{\lfloor \log_2 n \rfloor +2} -1) + 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{\lfloor \log_2 n \rfloor+1-j} \\ = c F_{\lfloor \log_2 n \rfloor +1} - 4 (F_{\lfloor \log_2 n \rfloor +2} -1) + 4 \times 2^{\lfloor \log_2 n \rfloor+1} \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{-j} \\ = c F_{\lfloor \log_2 n \rfloor +1} - 4 (F_{\lfloor \log_2 n \rfloor +2} -1) + 16 \times 2^{\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{-j-1}.$$

The same constant appears as in the lower bound. Now since the term $F_{\lfloor \log_2 n \rfloor}$ is asymptotically dominated by $2^{\lfloor \log_2 n \rfloor}$ (we have $F_{\lfloor \log_2 n \rfloor}\in o(2^{\lfloor \log_2 n \rfloor})$ because $F_{\lfloor \log_2 n \rfloor} \in\Theta(\varphi^{\lfloor \log_2 n \rfloor}))$ joining the upper and the lower bound we get for the asymptotics of this recurrence that it is

$$T(n)\in\Theta\left(2^{\lfloor \log_2 n \rfloor}\right) = \Theta\left(2^{\ \log_2 n}\right) = \Theta(n),$$ which, let it be said, could also have been obtained by inspection.

Remark. The evaluation of the constant is done by noting that the generating function of $$F_{j+1} 2^{-j-1}\quad \text{is}\quad\frac{1/2}{1-z/2-z^2/4}$$ which at $z=1$ evaluates to $\frac{1/2}{1-1/2-1/4} = 2.$ We have a certain flexibility as to what power of two to use in the constant but this does not affect the asymptotics.

This MSE link has a similar calculation.

Answer 2

In light of the detailed solution of @Marko Riedel, if you only want to show that $T(n)=O(n)$, you can make the (somewhat easier computation):

Base case: (ok)

Inductive Hypothesis: $T(k)\leq Ck$ for $k<n$ for some constant $c>0$.

Then, prove the inductive step: \begin{align*} T(n) &= T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4))+4n \\ &\leq T(n/2)+T(n/4) + 4n & \text{by monotonicity} \\ &\leq C(n/2)+C(n/4) + 4n \\ &=(3C/4+4)n \\ &=Cn & \star\star \end{align*}

Where $\star\star$ is true if $(3C/4+4)=C$ which works when $C=16$.

So, the moral of the story is that if you can guess that $T(n)=O(n)$ it is not hard to prove it by induction.

EDIT: One final note, it wasn't asked to get a $\Theta$ bound on $T(n)$, but it is pretty clear (by the recurrence) that $T(n)=\Omega(n)$ since $T(n)\geq 4n$. Then, combining this with the previous argument shows that $T(n)=\Theta(n)$.