3 ms·
Isn'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))
by arethuza 6y ago
Isn'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