$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...


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)$.

  • $\begingroup$ 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? $\endgroup$ – Michael Lugo Oct 1 '11 at 19:32
  • $\begingroup$ @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. $\endgroup$ – Sasha Oct 1 '11 at 20:00

Suppose we first study $$g(n) = f(n)-3$$ which has $g(0)=g(1)=0$ and $$g(n) = g(\lfloor n/2 \rfloor) + g(\lfloor n/4 \rfloor) + cn+3.$$ Then it is not difficult to see that for the binary representation of $n$ being $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ we have that for $n\ge 2,$ $$g(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} [z^j] \frac{1}{1-z-z^2} \left(3 + c\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}\right)$$ which in turn implies $$f(n) = 3 + \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} [z^j] \frac{1}{1-z-z^2} \left(3 + c\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}\right).$$ Now note that the polynomial term is the generating function of the Fibonacci numbers shifted down by one, so that this simplifies to an attractive exact formula for all $n$ which is $$f(n) = 3 + \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} \left(3 + c\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}\right) = 3 F_{\lfloor \log_2 n \rfloor+2} + c \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}.$$

Next we compute upper and lower bounds. For an upper bound consider a string of one digits, which gives the following bound which is actually attained and cannot be improved upon: $$f(n) \le 3 F_{\lfloor \log_2 n \rfloor+2} + c \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^{k-j} \\ = 3 F_{\lfloor \log_2 n \rfloor+2} + c \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} (2^{\lfloor \log_2 n \rfloor+1-j}-1) \\= c + (3-c) F_{\lfloor \log_2 n \rfloor+2} + c 2^{\lfloor \log_2 n \rfloor+1} \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{-j}.$$ Now the sum term converges to a limit. We have $$ \sum_{j=0}^\infty F_{j+1} 2^{-j} = \frac{1}{\sqrt{5}} \left(\varphi \sum_{j=0}^\infty (\varphi/2)^j - (-1/\varphi) \sum_{j=0}^\infty (-1/\varphi/2)^j\right) \\ = \frac{1}{\sqrt{5}} \left(\frac{\varphi}{1-\varphi/2}+\frac{1/\varphi}{1+1/\varphi/2}\right) =4.$$ For a lower bound consider a one followed by a string of zeros, giving $$f(n) \ge 3 F_{\lfloor \log_2 n \rfloor+2} + c \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{\lfloor \log_2 n \rfloor-j} =3 F_{\lfloor \log_2 n \rfloor+2} + c 2^{\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{-j}. $$ The sum term converges to four as before. We see that the dominant asymptotics in both bounds come from the two terms $$F_{\lfloor \log_2 n \rfloor+2} \quad\text{and}\quad 2^{\lfloor \log_2 n \rfloor}.$$ Note that $$F_n \sim \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n$$ which means that the power of two dominates, giving a final complexity of $$\Theta\left(2^{\lfloor \log_2 n \rfloor}\right) = \Theta\left(2^{\log_2 n}\right) = \Theta(n).$$ This MSE link points to a similar calculation.


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.