# How does the inequality $n/2^k ≤ 0$ become $n < 2^k$?

I'm going through a presentation on the topic of analysis of algorithms and I encountered the following inequalities as part of the steps being explained:

1. the loop stops: $n/2^k ≤ 0$
2. that is: $n < 2^k$
3. thus, when the loop stops: $k > ⌈lg n⌉$

(Note: For the sake of being explicit, $lg n$ is shorthand for $log_2 n$. Also, $n/2^k$ can be assumed to be integer division.)

Now, it's been a while for me, but from what I've been checking, it looks like the change from ≤ into < on step 2 might be a typo(?), except for the fact that it carries over to subsequent steps.

If it's not a typo, the only thing I can think of is that it's related to the 0 on the right when multiplying by $2^k$ on both sides of step 1, but I couldn't immediately find an identity or property that justified changing the signs from ≤ to < or ending with a non-zero value on the right-hand side.

Can someone explain what I'm missing between these steps?

The pseudo-code for the algorithm in question, quoted from the slide, is below:

p = 1;
e = a;
N = n;
while (N > 0) {
if (n % 2 != 0)
p *= e;
e *= e;
N /= 2;
}


It's analyzed to be in the order of O(lg n). A few notes for clarity, though not necessarily relevant to the original question:

1. n is the input size of the problem instance, and it's a non-negative integer (e.g. 50)
2. statements like p *= e are shorthand for $p \leftarrow p * e$
3. a is not defined anywhere, but can be assumed to be an arbitrary, though unknown, integer constant
• This must be a typo. If the first condition is $n/2^k \le 1$, everything falls into place. – Hans Engler Jan 15 '17 at 23:02
• Well, if $n$ is negative, then it's true, since $n < 0 < 2^k$. But if $n$ is positive, then the first inequality $\frac{n}{2^k} \leq 0$ is false. – MathematicsStudent1122 Jan 15 '17 at 23:03
• You need to provide more context. The conclusion follows iff $n/2^k$ is assumed to mean integer division or, equivalently, if you change it to $\lfloor n/2^k \rfloor$. In that case $\lfloor n/2^k \rfloor \le 0 \iff \lfloor n/2^k \rfloor \lt 1 \iff n \lt 2^k$. – dxiv Jan 15 '17 at 23:03
• @dxiv I'm quoting the presentation slides, so I don't think it'd be correct to speculate by adding things that are not present. Additional slide info is a statement prior to the steps, saying "Termination condition: N ≤ 0" – code_dredd Jan 15 '17 at 23:05
• @MathematicsStudent1122 The variable n is a positive integer, since this is on the topic of algorithm analysis for problem instances of size n. – code_dredd Jan 15 '17 at 23:06

It is customary to assume that loop counters are integers (in fact, the loop would never end otherwise). In that context the pseudo-code N = N / 2; denotes integer division with truncation towards $0$, and is equivalent to the math assignment $N \leftarrow \lfloor N/2 \rfloor$.
Under this interpretation the RHS in $\lfloor n/2^k \rfloor \le 0$ is an integer, so the condition $\lfloor n/2^k \rfloor \le 0$ is equivalent to $\lfloor n/2^k \rfloor \lt 1$. By definition of $\lfloor \cdot \rfloor$ the latter is equivalent to $n/2^k \lt 1 \iff n \lt 2^k$.