I am deriving $\left\lceil \log_2 (\frac{n}{2})\right \rceil$, and I'm unsure on whether this becomes $\left\lceil \log_2 n \right\rceil$ – $\left\lceil \log_2 2 \right\rceil$= $\lceil \log_2 n \rceil-1$
or whether it becomes $\left\lceil \log_2n – \log_2 2 \right\rceil$ = $\lceil \log_2 n -1\rceil$ = $\lceil \log_2 n \rceil -1$?
I see that both come to the same conclusion, however, I am unsure on whether the first method breaks logarithmic laws? This I assume will be able to be applied to the floor function as well I assume?
Thanks for any clarification.
Best Answer
Undisputably,
$$\left\lceil\log_2\frac n2\right\rceil=\left\lceil\log_2n-1\right\rceil.$$
Now the question is if you can pull out the $-1$ term to obtain
$$\left\lceil\log_2n\right\rceil-1.$$
The answer is true, you can move an integer constant in and out: $\lceil x+k\rceil=\lceil x\rceil+k$. This is because with $x=m-z$ where $z\in[0,1)$,
$$\lceil x+k\rceil=\lceil m-z+k\rceil=m+k=\lceil m-z\rceil+k=\lceil x\rceil+k.$$
This doesn't work with a non-integer constant, in general $\lceil x+y\rceil\ne\lceil x\rceil+\lceil y\rceil\ne\lceil x\rceil+y\ne x+\lceil y\rceil\ne x+y$.