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})$

Question

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.

Answer 1

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*} $$