The function is defined by $f :\mathbb{Z}^+\rightarrow\mathbb{Z}^+$ and $f(n) = 2f(\lfloor{\frac{n}{2}}\rfloor)+1$ for $n \geq 2$ with $f(1) = 1$.
How to prove that $f(n) = O(n)$ for $n \geq 1 $?
base on the calculations,
$f(1) = 1$,
$f(2) = f(3) = 3$,
$f(4) = ... =f(7) = 7 $
I saw that the $2^{k}$term to $2^{k+1} -1$ term is equal to $2^{k+1}-1$ where $k=1,2,...n$
But i have no idea how i starts the proof. Thanks a lot
I claim that
$$2^{k-1}\le n<2^k\implies f(n)=2^k-1.$$
By induction, we have
base case: $$2^{1-1}\le1<2^1\implies 1=2^1-1$$ is true.
Inductive step:
$$2^k\le n<2^{k+1}\implies 2^{k-1}\le\left\lfloor\frac n2\right\rfloor<2^k\implies 2f\left(\left\lfloor\frac n2\right\rfloor\right)+1=2(2^k-1)+1=2^{k+1}-1.$$
Now it should be clear that
$$n\le f(n)<2n$$ and $$f(n)=\Theta(n).$$
The function $f$ is what you get by setting all bits of $n$ (e.g. $100101011_b\to111111111_b$).