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$
  • $\begingroup$ This must be a typo. If the first condition is $n/2^k \le 1$, everything falls into place. $\endgroup$ – Hans Engler Jan 15 '17 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$ – MathematicsStudent1122 Jan 15 '17 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 Jan 15 '17 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 Jan 15 '17 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 Jan 15 '17 at 23:06
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.