Good day, we are currently covering basic principles for algorithm optimisation and we were tasked with explaining the following problem.

Assume $x,y \in \Bbb R$. How much can the following two integers differ:

$\lfloor x \rfloor - \lfloor y \rfloor$ and $\lfloor x-y \rfloor$

These can clearly be equal but I am not quite sure how to explain or approach the explanation of how they differ.

They can differ by at most the difference between the integer parts of $x$ and $y$ but I do not think that this is enough.


Write $x=n+a$ and $y=m+b$ with $n,m\in\mathbb Z$ and $0\le a,b<1$. $\lfloor x\rfloor-\lfloor y\rfloor$ is obviously $n-m$, while $$\lfloor x-y\rfloor=\lfloor n-m+(a-b)\rfloor=n-m+\lfloor a-b\rfloor$$ From the bounds on $a,b$ we see that $-1<a-b<1$, so $\lfloor a-b\rfloor$ is 0 if $0\le a-b<1$ and $-1$ otherwise.

Therefore $\lfloor x\rfloor-\lfloor y\rfloor$ is either equal to or one greater than $\lfloor x-y\rfloor$.


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.