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

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.
