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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ You should replace the image with text. $\endgroup$ Commented Oct 12, 2017 at 11:31

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Where does it say that $[x]$ in $Increment$ is the greatest integer less than or equal to $x$? $\endgroup$ Commented 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$ Commented Oct 12, 2017 at 12:15
  • $\begingroup$ Okay! That solves my confusion. $\endgroup$ Commented 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$ Commented 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$ Commented 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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.