# What is the asymptotic bound for this recursively defined sequence?

$f(0) = 3$

$f(1) = 3$

$f(n) = f(\lfloor n/2\rfloor)+f(\lfloor n/4\rfloor)+cn$

Intuitively it feels like O(n), meaning somewhat linear with steeper slope than c, but I have forgot enough math to not be able to prove it...

-
add comment

## 1 Answer

In your recurrence, set $n=4m$ for an integer $m$. Then $f(4m) = f(2m)+f(m) + 4 c m$. From your original equation, it's easy to determine $f(1) = 3$, $f(2) = 6 + 2c$, $f(4) = 9 + 6 c$.

Now, let $g(n) = f(2^n)$, so the equation translates into $g(n+2) = g(n+1) + g(n) + c 2^{n+2}$. The solution to this equation is easy to find. $$g(n) = c_1 F_n + c_2 L_n + c 2^{n+2}$$ where $F_n$ are Fibonacci numbers, and $L_n$ are Lucas numbers. Asymptotically, Fibonacci and Lucas numbers grow only as $\phi^n$, and since $\phi < 2$, the dominating term is $c 2^{n+2}$. Rolling back, $f(m) \sim 4 c m + o(m)$.

-
I'm not sure if you can just say "rolling back" like that here. From computing $g(n)$ out to $2^{10}$ (which I admit isn't that far) it seems like $f(2^n) \sim c 2^{n+2}$ as $n \to \infty$ but, say, $f(3 \times 2^n)$ isn't necessarily approaching $c (3 \times 2^{n+2})$. Is there some theorem encapsulated in the phrase "rolling back" that I'm unaware of? –  Michael Lugo Oct 1 '11 at 19:32
@MichaelLugo Well, let $h(n) = f(3 \times 2^n)$, then $h(n+2) = h(n+1) + h(n) + 3 c 2^n$ just as well, and $h(n) \sim 4 c ( 3 \times 2^n)$, so the result would hold. You may ask what about $f(3^n)$, but I suspect the story will turn out the same by some regularity of the solution, but I do not have a satisfactory answer for this. –  Sasha Oct 1 '11 at 20:00
add comment