1
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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