0
$\begingroup$

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
$\endgroup$
12
  • $\begingroup$ This must be a typo. If the first condition is $n/2^k \le 1$, everything falls into place. $\endgroup$ Commented Jan 15, 2017 at 23:02
  • $\begingroup$ 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. $\endgroup$ Commented Jan 15, 2017 at 23:03
  • 1
    $\begingroup$ 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$. $\endgroup$
    – dxiv
    Commented Jan 15, 2017 at 23:03
  • $\begingroup$ @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" $\endgroup$
    – code_dredd
    Commented Jan 15, 2017 at 23:05
  • $\begingroup$ @MathematicsStudent1122 The variable n is a positive integer, since this is on the topic of algorithm analysis for problem instances of size n. $\endgroup$
    – code_dredd
    Commented Jan 15, 2017 at 23:06

1 Answer 1

1
$\begingroup$

The following collects bits and pieces gathered in the comments to provide a formal answer.

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

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .