Return to Answer

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.

(Sorry, that should be "Time" not "Speed".)

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.

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.

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.

(Sorry, that should be "Time" not "Speed").

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*n. C determines the angle.
• O(n^2) is really (C*n)^2. 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(logn). Or you could use an unsorted list and re-sort after every insert or deletion at O(nlogn). 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.

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.

(Sorry, that should be "Time" not "Speed".)

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.

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*n. C determines the angle.
• O(n^2) is really (C*n)^2. 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(logn). Or you could use an unsorted list and re-sort after every insert or deletion at O(nlogn). 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.

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.

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.

(Sorry, that should be "Time" not "Speed").

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*n. C determines the angle.
• O(n^2) is really (C*n)^2. 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(logn). Or you could use an unsorted list and re-sort after every insert or deletion at O(nlogn). 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.