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.

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

share|improve this question
add comment

2 Answers

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

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

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.

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