3 ms·
The way in which I like to often think about these things in practice is with "hidden" constant factors. For example, you can think of the O(1) algorithm as rea
by ls65536 6y ago
The way in which I like to often think about these things in practice is with "hidden" constant factors. For example, you can think of the O(1) algorithm as really taking O(1 * K1) time, and the O(n) algorithm taking O(n * K2) time to complete. For different algorithms, K1 and K2 will almost certainly be distinct, and may even differ by significant amounts. Of course, if K1 is less than K2, then the value of "n" is irrelevant, and the O(1) algorithm always completes faster. But if K1 is greater than K2, as is the case quite often, then this really depends on the nature of what "n" is in practice, and whether or not it is larger than the value of K1/K2. This of course still ignores any other, often important, considerations beyond just run time such as memory consumption (which may also affect run time indirectly), but I find it's a good starting point when trying to reason about when O(n) can run faster than O(1) in various real-world scenarios.
It's a good reminder to always try to understand your likely workloads as well as possible (know your "n"), and to get good measurements (what are K1 and K2 values) before prematurely optimizing these kinds of things.
- arethuza 6y agoIsn't that already built into the definition of O? "f(x) ∈ O(g(x)) as there exists c > 0 and x0 such that f(x) ≤ cg(x) whenever x ≥ x0" Saying f(x) is O(g(x)) doesn't say anything about how those two functions compare below x0? https://en.wikipedia.org/wiki/Big_O_notation https://en.wikipedia.org/wiki/Big_O_notation Edit: Not trying to be snarky - just trying to check whether my 30+ year old memory of education on such matters is even vaguely correct... :-) Edit2: Added "memory of" - I'm pretty sure what I was taught was correct, just my memory of it that is all too fallible.
- cyphar 6y agoYou are correct, the point being made was that a lot of people aren't aware of that and just take it as gospel that O(1) algorithms must be faster than O(n) ones -- but, as you said, big-O notation only says that is true after n goes above some threshold n0 which may be (and usually is) very large. After all, the most efficient (in terms of big-O) known algorithm for multiplying two numbers uses a 1729-dimensional Fourier transform and only becomes more efficient once the numbers involved are significantly larger than the number of atoms in the universe[1]. [1]: https://en.wikipedia.org/wiki/Galactic_algorithm https://en.wikipedia.org/wiki/Galactic_algorithm