Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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