Recurrence with $\lfloor n/2 \rfloor$

Question

For $C_n=C_{n/2} + 1 $. where $C_1 = 1$ and $n\ge2$

$C_n$ will be about $\log n$.

If $n/2$ is intepreted as $\lfloor n/2 \rfloor$ for a recurrence question. The solution becomes $\lfloor \log_2n \rfloor + 1$ due to 'binary representation'.

I need to solve $C_n$ = $2C_{n/2} + n $ with correspondence to the binary representation of N.

Answer 1

For the first equation: try to prove (induction is great here) that if the binary representation of $n$ has $k$ digits then $C_n=k$.