2
$\begingroup$

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

2 Answers 2

5

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

  • 0
    @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.2011-10-01
0

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.