How do you justify making algorithm subroutines more efficient when Big-O notation only includes the dominant term?

Question

I don't really understand time complexity, and wanted some clarification in this hypothetical situation.

If I were being given items one by one, and I wanted a list of them all in the reverse order I got them in, I could add each item to an ArrayList, then reverse it. Both of these operations are $O(n)$ in time complexity, and therefore my total is $O(2n)$, which is just $O(n)$.

However, I could also add each item as I got it to a Stack, and since Stacks are LIFO, it's already reversed once I have all of the items. This skips the $O(n)$ ArrayList reversing, but is still $O(n)$ overall since getting the n items was $O(n)$.

I think the second option would be better, since I'm avoiding an $O(n)$ subroutine, but how can I say that I have made my algorithm more efficient?

In the context of explaining how my second algorithm is more efficient, is it appropriate to just say I have made it more efficient by removing an $O(n)$ subroutine?

Answer 1

Asymptotic notation is not fine-grained enough capture the difference between $n$ and $2n$ operations, and there are good theoretical reasons not to care about multiplicative constants unless we want to specify the nitty-gritty details of the model of computation at hand and of our algorithms.

That said, you could say that both algorithms require $\Theta(n)$ time but the second version has a "smaller hidden multiplicative constant"*.

---

*Be careful on how the stack and the array lists actually implemented when you estimate the number of operations down to multiplicative constants. There might be more going on under the surface than what meets the eye. For example a common implementation of a list/stack that is backed by a dynamic array might have a final capacity of $2n$, and the overall number of elements written to it might be about $4n$.

Answer 2

You might measure that a particular implementation of an algorithm on a particular computer takes say $315 n^2$ nanoseconds, plus/minus 10%. And an implementation of a different algorithm on the same computer is measured to take $409 n^2$ nanoseconds, plus/minus 6%. I guess you will prefer the first algorithm.

Big-O notation and asymptotic complexity ignores what particular computer you are using, what programming language and compiler / interpreter etc. In this case it would be just interested in the $n^2$ term. So both algorithms would be judged to be equivalent in execution time.

This is quite reasonable because otherwise you'd find it hard to judge an algorithm independent of the hardware that is used. Actually, the difference in speed in my example is so little, it is absolutely possible that on a different computer the second algorithm would be faster.

Note that if you want to make an algorithm just twice as fast, you often have the choice to write code that runs faster (which may cost you because it can be hard work to make code faster), or instead pay for a faster computer that runs twice as fast. If an algorithm is asymptotically slower, buying a faster computer isn't going to help.