# Find an asymptotic bound for $T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+…+T(\frac{n}{2^k})$

Given is the following recurrence relation:

$$T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+...+T(\frac{n}{2^k})$$

where $$k$$ is some constant and $$n = 2^t$$ for some $$t\in \mathbb{Z}$$.

I'm trying to find an asymptotic bound for $$T(n)$$.

My work so far:

First, I've tried to guess and prove by induction. Then, I tried to solve using a recursion tree, but I couldn't find any obvious pattern to follow.

• Try proving an upper bound of the form $Cn^2$ by induction. – Yuval Filmus Nov 15 '18 at 17:18
• You can find a proper value for $C$ while doing induction. – Apass.Jack Nov 15 '18 at 17:41

Assuming an appropriate base case, you can prove that $$T(n) \leq \frac{3}{2} n^2$$. (If this doesn't work for the base case, just increase $$3/2$$ to a large enough constant.)
Indeed, assuming this holds for $$m < n$$, we have \begin{align*} T(n) &= n^2 + T(\tfrac{n}{2}) + T(\tfrac{n}{4}) + \cdots + T(\tfrac{n}{2^k}) \\ &\leq n^2 + \frac{3}{2} \frac{n^2}{4} + \frac{3}{2} \frac{n^2}{4^2} + \cdots + \frac{3}{2} \frac{n^2}{4^k} \\ &= n^2 \left(1 + \frac{3}{2} \left(\frac{1}{4} + \frac{1}{4^2} + \cdots + \cdots + \frac{1}{4^k}\right)\right) \\ &< n^2 \left(1 + \frac{3}{2} \cdot \frac{1}{3}\right) \\ &= \frac{3}{2} n^2. \end{align*}