0
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Oct 27, 2023 at 22:49
  • $\begingroup$ Well you have enough information to solve it using my answer, don't you? $\endgroup$
    – Nathaniel
    Oct 27, 2023 at 23:22

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.