Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer 1

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

share|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
add comment

Your Answer

 
discard

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.