1
$\begingroup$

I'm trying to find a closed formula for the below recurrence relation:

For the first one, $n$ is some power of 2

$$T(n) = \begin{cases} 4 & \text{if $n=1$} \\ 2T(\frac{n}{2}) +4 & \text{else} \end{cases}$$

$$T(n) = \begin{cases} 1 & \text{if $n=0$} \\ T(n-1) +3^n & \text{else} \end{cases}$$

I tried to use the substitution and tree methods but I'm not sure what I'm doing and I think I get the wrong answer.

$\endgroup$
  • $\begingroup$ For the first $T$, $T(n)+4=2(T(n/2)+4)$. So $T(n)+4$ is a geometric series with ratio 2. For the second $T$, $T(n)=3^n + 3^{n-1} + \cdots + 1$. $\endgroup$ – John L. May 15 at 2:51
0
$\begingroup$

When you are not sure of whether you get the right answer, you can write a simple program in any of your favorite languages to double check.

For example, for the first function, I became pretty confident that I got the right answer once I had run the following script in Python.

def T(n):
    if n == 1: return 4
    return 2 * T(n // 2) + 4

for i in range(1, 20):
    print(T(2 ** i), 2 ** (i + 3) - 4)

Similarly, I ran the following script for the second function.

def S(n):
    if n == 0: return 1
    return S(n - 1) + 3 ** n


for i in range(20):
    print(S(i), (3 ** (i + 1) - 1) // 2)
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes! I thought about doing so but wasn't sure. Will try now. If you can write in hidden text the formulas you got so I can compare it later it would be great :) $\endgroup$ – Combinatoric May 15 at 7:01
  • $\begingroup$ If you can recognize or guess Python, the formulas are right there. $\endgroup$ – John L. May 15 at 7:04

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.