$f(n)=2f(\lfloor{n\over2}\rfloor)+1$ . Prove that $f(n)=O(n)$. $f(n)=2f(\lfloor{n\over2}\rfloor)+1$ where $n$ is positive integer and $f:Z^+\to Z^+$. Prove that $f(n)=O(n)$.
Attempts: I have figured the case that for $n=2^k$, $f(n)=2n-1$ which can be obtainly by simple recurrance. But $n$ is any positive integer, i think only the case $n=2^k$ can't really help to the prove. Any hints or solution are welcome.
 A: Hint: Prove that if $2^k \leq n<2^{k+1}$, then $f(n)=2^kf(1)+2^k-1$ using induction.
A: Reading your attempt I assume that $f(1)=1$ but you might as well work with $f(1)$ being any other integer. Suppose $n= 2^k + l$ with $0\leq l<2^k$. Then $f(n)=2f(2^{k-1}+l_1)+1$ with $l_1\in\mathbb{Z}$ and $0\leq l_1\leq l/2<2^{k-1}$. By induction: 
$f(n)=2^k f(1)+2^{k-1}+\ldots+1=f(2^k)=2^{k+1}-1\leq 2n-1$.
A: This is a very simple case of the Master theorem that can be solved exactly, the way that was done here. Let the binary representation of $n$ be given by
$$ n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$ Use $T(n)$ instead of $f(n)$ for consistency with some of the other SE material. 
Now with $T(0)=0$, we have $$ T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} (2^j \times 1) =
2^{\lfloor \log_2 n \rfloor+1} -1.$$
Observe that $$ \log_2 n - 1 < \lfloor \log_2 n \rfloor \le \log_2 n$$
so that $$n < 2^{\lfloor \log_2 n \rfloor+1} \le 2n
\quad \text{and} \quad
n-1 < T(n) \le 2n-1.$$
This allows us to conclude that $$T(n) \in \Theta(n).$$
A: Hint: Show that the property $f(n)\leqslant cn-1$ is hereditary, for every fixed positive $c$. Choosing $c$ large enough yields $f(n)=O(n)$.
