# Limit of $\frac{f(n)}{2^n}$ where $f(n) = 2f(n-1) + g(\lfloor \frac{n}{2} \rfloor)$

This is inspired by a question from stackoverflow, about computing the time complexity of two recursive methods.

The recurrence relation in that question is

$$f(n) = 2f(n-1) + g(\lfloor \frac{n}{2}\rfloor)$$

$$g(n) = f(n-1) + g(\lfloor \frac{n}{2}\rfloor), n \ge 2$$

$$f(0) = g(0) = g(1) = 1$$

I believe I have been able to show that $f(n) = \Theta(2^n)$.

We can also show that $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 2$

We can show that $\frac{f(n)}{2^n}$ is convergent (it is monotonic and bounded).

Empirical evidence shows that $\frac{f(n)}{2^n}$ likely converge to ~$3.22698962391$.

I was wondering if there is a way of finding a closed form for this limit?

-
Presumably your recurrence for $g$ is only for $n \ge 2$, since for $n=1$ it conflicts with $g(1)=1$. –  Robert Israel Mar 29 '13 at 19:16
@RobertIsrael: You are right. I have edited. Thanks. –  Knoothe Mar 29 '13 at 19:17
add comment

## 1 Answer

Actually I get $f(n)/2^n \approx 2.663652377$. I doubt that this has a closed form.

-
Oh, perhaps my code has a bug (and I stopped after a 1000 terms, when the values stopped changing). What did you use for computation? I am guessing it is some professional mathematical package? –  Knoothe Mar 29 '13 at 19:21
add comment