News for hackers. Stuff that matters.
Re:14,000x Speedup (2015) by arethuza on Tuesday October 13, 2020 @10:34AM (#24765923)
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

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.

Re:14,000x Speedup (2015) by cyphar on Tuesday October 13, 2020 @10:43AM (#24766034)
You 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

Re:14,000x Speedup (2015) by pmiller2 on Tuesday October 13, 2020 @04:44PM (#24770102)
Interesting (coincidental?) appearance of 1729 here in a numerical algorithm.
Re:14,000x Speedup (2015) by arethuza on Tuesday October 13, 2020 @10:51AM (#24766104)
That "significantly" is quite the understatement!