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

-
Try showing that $f$ is monotone and that $f(2n)$ is not too much bigger than $f(n)$. – Louis Feb 28 '13 at 9:55

Hint: Prove that if $2^k \leq n<2^{k+1}$, then $f(n)=2^kf(1)+2^k-1$ using induction.

-
how you do the induction?If n=r is true, how to procced to n=r+1? – John Feb 28 '13 at 10:17
Induct on $k$, not $n$ – Ivan Loh Feb 28 '13 at 10:38

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

-
the second sentence $f(n)=2f(2^{k-1}+l_1)+1$ is not true as you missed $\lfloor\rfloor$ – John Feb 28 '13 at 10:00
@John: I just set $l_1=\lfloor l/2 \rfloor$, this makes the notation for the induction easier (You'll have $0\leq l_j<2^{k-j}$). – Michalis Feb 28 '13 at 10:01

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

-

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

-