Log Laws with Ceiling and Floor Function

Question

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.

Answer 1

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

Answer 2

The second method is the correct one. Before you can apply the floor function, you need to evaluate the logarithm. The logarithm can be simplified, as you did

$$\log_2\left(\frac{n}2\right)=\log_2 n - \log_2 2$$

and hence your second solution follows.

Note that the used formula (with $a=\log_2 n$ and $x=- \log_2 2$)

$$\lfloor a+x \rfloor = \lfloor a \rfloor +x$$

only works when $x \in \mathbb Z$ (as in this case, where $\log_2 2=1$).

There are no generally useful rules that combine logarithms and floor functions. Your first solution looks like you wrote something down that "looks good", but in fact isn't.

That may become clear if you substitute $\frac{n}3$ for $\frac{n}2$ in your initial formula.

The correct second method leads to

$$\left\lfloor\log_2\left(\frac{n}3\right)\right\rfloor=\lfloor\log_2 n - \log_2 3\rfloor = \lfloor\log_2 n - 1.58496\ldots\rfloor$$

which cannot be further simplified.

The incorrect first method leads to

$$\left\lfloor\log_2\left(\frac{n}3\right)\right\rfloor=\lfloor\log_2 n\rfloor - \lfloor \log_2 3\rfloor = \lfloor\log_2 n\rfloor - \lfloor 1.58496\ldots\rfloor = \lfloor\log_2 n\rfloor - 1$$

Now, for some values of $n$ both formulas $\lfloor\log_2 n - \log_2 3\rfloor$ and $\lfloor\log_2 n\rfloor - 1$ give the same value, like for $n=7$. But they also give different values for other values, like $n=5$.

This should show by example that your first solution is not generally correct, it uses a simplification that is just not correct for all values. In the specific case of this problem problem, it turned out to be correct because the crucial value $\log_2 2$ was an interger, but generally this will not be the case.