1
$\begingroup$

Take a look at this excerpt from the Algorithm Design Manual, 2nd Edition by Skiena.

enter image description here enter image description here

I have circled the confusing bit. Basically, everything is understandable to me, until that part. How can $Increment([m+1/2])$ be rewritten as $Increment([m])$? Clearly, if m is an integer, then the algorithm will not treat $m+1/2$ as $m$ and return $m+1$. Instead, $Increment$ is going to go into the $else$ clause and return $m+1/2+1$, which is clearly not $m+1$. Am I missing something here?

$\endgroup$
1
  • 1
    $\begingroup$ You should replace the image with text. $\endgroup$
    – fade2black
    Oct 12, 2017 at 11:31

1 Answer 1

1
$\begingroup$

How can $Increment([m+1/2])$ be rewritten as $Increment([m])$?

Recall that $[x]$ means the greatest integer less than or equal to $x$.

Since $m$ is integer, $m$ is the less than $m+0.5$ and $m+0.5 < m+1$. Thus the the greatest integer less than or equal to $m+0.5$ is $m$.

$\endgroup$
6
  • $\begingroup$ Where does it say that $[x]$ in $Increment$ is the greatest integer less than or equal to $x$? $\endgroup$
    – Sandi
    Oct 12, 2017 at 12:05
  • $\begingroup$ $[x]$ is the greatest integer less than or equal to $x$. It is a standard definition, not specific to your problem. $\endgroup$
    – fade2black
    Oct 12, 2017 at 12:15
  • $\begingroup$ Okay! That solves my confusion. $\endgroup$
    – Sandi
    Oct 12, 2017 at 12:16
  • $\begingroup$ Nitpick: note that the textbook uses the $\lfloor \cdot \rfloor$ notation, which is less ambiguous than $[\cdot ]$. Only the OP used the latter notation. $\endgroup$
    – chi
    Oct 12, 2017 at 12:43
  • $\begingroup$ @chi I don't see any ambiguity in both $\lfloor \cdot \rfloor$ and $[\cdot]$, both are well defined notations, though agree that textbook uses $\lfloor \cdot \rfloor$ instead of $[\cdot]$. They coincide when defined on the set of positive reals, though different on the set of negative reals. $\endgroup$
    – fade2black
    Oct 12, 2017 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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