Given is the following recurrence relation:


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.

  • $\begingroup$ Try proving an upper bound of the form $Cn^2$ by induction. $\endgroup$ Commented Nov 15, 2018 at 17:18
  • $\begingroup$ You can find a proper value for $C$ while doing induction. $\endgroup$
    – John L.
    Commented Nov 15, 2018 at 17:41

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.