Struggling with Recurrence Relation using Telescoping Approach

Question

I have the following recurrence relation that I am trying to solve using the telescoping approach: $T(n) = \begin{cases} T(\frac{n}{4})+ n^2 & \text{for } n \geq 4 \\ 1 & \text{otherwise} \end{cases}$

I have this so far:

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

$T(\frac{n}{4}) = T(\frac{n}{16}) + (\frac{n^2}{16})$

$T(\frac{n}{16}) = T(\frac{n}{64}) + (\frac{n^2}{256}) $ ... up to $T(n) = 1$

I know I am supposed to now write $T(n)$ as a sum of these expansions but I dont seem to be doing it right. I have:

$T(n) = n^2 + (\frac{n}{4})^2 + (\frac{n}{16})^2 + (\frac{n}{64})^2$ and so on.

Sorry for the poor formatting of my question, I am new to Stack Exchange. Please give me suggestions on formatting so I can edit it.

Answer 1

I am not so sure what the problem is: is it a problem on writing the formula with the sum, or finding a closed formula for the sum?

In the first case, you could write either: $$T(n) = n^2 + \left(\frac{n}4\right)^2 + \left(\frac{n}{16}\right)^2 ... + 1$$

but that hides the number of terms.

Another possibility is writing:

$$T(n) = \sum\limits_{k=0}^{\log_4 n}\left(\frac{n}{4^k}\right)^2$$

Now for solving this, you just need to note that $T(n) = n^2\sum\limits_{k=0}^{\log_4 n}\frac{1}{16^k}$.

You can either find a formula for the sum: $$\sum\limits_{k=0}^{\log_4 n}\frac{1}{16^k} = \frac{1-\frac{1}{16^{\log_4 n + 1}}}{1 - \frac{1}{16}} = \frac{16-\frac{1}n}{15}$$ or simply an upper bound: $$\sum\limits_{k=0}^{\log_4 n}\frac{1}{16^k} \leqslant \sum\limits_{k=0}^{+\infty}\frac{1}{16^k} = \frac{1}{1- \frac{1}{16}} = \frac{16}{15}$$

• Nancy Drake: Thanks for your help. The question I was asked is: Given the following recurrence equation of T(n), express T(n) in an asymptotic big-O function from. Use the telescoping approach. State any simplifying assumption you are making. It suffices to derive the functional form only; there is no need to prove it by the formal definition of big-O.
• Nathaniel: Well you have enough information to solve it using my answer, don't you?