# Problems that become far easier when restricted to only integer values

I know that there are some problems that are very hard to solve in general, but become much easier and asymptotically faster if restricted to only integer values.

One such example would be sorting which can be done in O(n+M) if only integer values are allowed.

Another example (I think) is the undirected single source shortest path problem which seems to be solvable in linear time if all weights are positive integers.

My question now is which problems are significantly easier to solve if restricted to integer values (and why?)

Note: I obviously don't expect a complete listing, I just want to understand the general principle behind the speed up by restricting the problem space to integers.

• 1. When you say "restricted to only integer values", do you really mean "restricted to only small integer values"? None of your examples actually works for arbitrary integers; the claimed speed-up is only possible if it's known that the values are small integers. 2. Despite your qualification, I'm not sure this question will have a good answer; it seems like it might be too broad to answer. I'm not sure you're going to get a single answer/principle that explains all instances of this phenomenom, as different algorithms may be fast for different reasons. I guess we'll see. – D.W. Jun 27 '16 at 19:37
• @D.W. Actually the single source algorithm by Thorup I linked is mostly independent on Integer size (assuming constant time multiplication). But yes, I expect most answers, if I get any, to be restricted to small integers. And yes, I probably won't get a grand theory of Integer restriction in the answers, but I find restricted cases interesting and hope to get some food for thought at least. – JeD Jun 27 '16 at 20:03

• Some algorithms are faster when dealing with small integers, because you can use small integers as the index into an array.

• Some algorithms are faster when dealing with positive integers, because the set of positive integers has the property that it does not contain any infinite decreasing chains: any set of positive integers has a minimum.

• Some algorithms are faster when dealing with integers because they assume a computational model where you can add or multiply integers in $O(1)$ time. It is dubious whether these algorithms are truly faster in practice, as that assumption isn't literally true, but they might be.

• Some algorithms are faster (or simpler) when dealing with integers because integers can be not only compared, but also hashed, and the ability to hash items increases the range of options available to the algorithm designer. See the nuts-and-bolts problem for an example vaguely of this form (there are probably better examples).

There are probably many other principles I'm not thinking of right now.

Most of the cases I know of involve only a $O(\lg n)$ speedup. However, be warned that asymptotic $O(\lg n)$ speedups are not very robust, for several reasons. Just because algorithm A is asymptotically faster than algorithm B by a factor of $\Theta(\lg n)$ doesn't mean it'll be faster in practice; it might be slower in practice, because of constant factors or because of considerations ignored in the theoretical analysis (e.g., caching effects, the memory hierarchy, and so on). Also, often the $O(\lg n)$ speedup results you see in this area will be dependent on a particular computational model and might not carry over to other computational models.

So, it's not clear how much weight you should put on this, if you are motivated by practical concerns.