"For small values of n, O(n) can be treated as if it's O(1)"

Question Detail: 

I've heard several times that for sufficiently small values of n, O(n) can be thought about/treated as if it's O(1).

Example:

The motivation for doing so is based on the incorrect idea that O(1) is always better than O(lg n), is always better than O(n). The asymptotic order of an operation is only relevant if under realistic conditions the size of the problem actually becomes large. If n stays small then every problem is O(1)!

What is sufficiently small? 10? 100? 1,000? At what point do you say "we can't treat this like a free operation anymore"? Is there a rule of thumb?

This seems like it could be domain- or case-specific, but are there any general rules of thumb about how to think about this?

Asked By : rianjs

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35385

Answered By : Schwern

All orders of magnitude involve a constant $C$, several of them actually. When the number of items are large enough that constant is irrelevant. The question is whether the number of items is small enough for that constant to dominate.

Here's a visual way to think about it.

All have a startup constant which determines their starting point on the Y axis. Each also has a critical constant $C$ dominating how fast they will increase.

• For $O(1)$, $C$ determines the time.
• $O(n)$ is really $C \times n$, where $C$ determines the angle.
• $O(n^2)$ is really $(C \times n)^2$, where $C$ determines the sharpness of the curve.

To determine which algorithm you should use, you need to estimate the spot where the runtimes intersect. For example, an $O(1)$ solution with a high startup time or a high $C$ will lose to an $O(n)$ solution with a low startup time and a low $C$ at fairly large numbers of items.

Here's a real world example. You have to move a bunch of bricks across a yard. You can move them a few at a time with your hands, or go get a huge, slow backhoe to lift and drive them over in one trip. What is your answer if there are three bricks? What is your answer if there are three thousand?

Here's a CS example. Let's say you need a list which is always sorted. You could use a tree which will keep itself in order for $O(\log{n})$. Or you could use an unsorted list and re-sort after every insert or deletion at $O(n \log{n})$. Because tree operations are complicated (they have a high constant), and sorting is so simple (low constant), the list will likely win out to hundreds or thousands of items.

You can eyeball this sort of thing, but in the end benchmarking is what will do it. You also have to eyeball how many items you'll typically have, and mitigate the risk of being handed more. You'll also want to document your assumption like "performance will degrade rapidly over $X$ items" or "we assume a maximum set size of $X$".

Because these requirements are subject to change, it's important to put these sorts of decisions behind an interface. In the tree/list example above, don't expose the tree or list. That way, if your assumptions turn out to be wrong, or you find a better algorithm, you can change your mind. You can even do a hybrid and dynamically switch algorithms as the number of items grows.