Re:Learn Big-O and stop hacking your way through algorithms
by taeric on Thursday August 20, 2020 @06:30PM
(#24229786)
Amusingly, it isn't that simple. 5000n will be larger than n! for several n, after all.
And it is often worth realizing that often you can shave time for space, but the setup costs aren't zero. Nor do you always have the space to setup. (For fun in this vein, lookup sortation networks.)
Re:Learn Big-O and stop hacking your way through algorithms
by quickthrower2 on Thursday August 20, 2020 @06:24PM
(#24229730)
The first example in that link is inside a compiler, so if compiler engineers can make mistakes that makes me feel better! I read it and I think it basically comes down to don’t concat strings for intermediate results, do it at the end.
Re:Learn Big-O and stop hacking your way through algorithms
by lern_too_spel on Thursday August 20, 2020 @06:37PM
(#24229834)
I see other people pointing out that it isn't true for small n, but this isn't true for large n either. The article's binary search implementation is O(n!) (and also O(log(n)), among many others). Its linear search is O(n) (and many others). I can find an N large enough such that the binary search will outperform the linear search for any n>N.
Re:Learn Big-O and stop hacking your way through algorithms
by xxpor on Thursday August 20, 2020 @06:41PM
(#24229867)
Sure, but that's not really the point. It's more running more code == probably bad for speed. There's obviously a lot of detail there, like time/space tradeoffs, large constants, etc.
Re:Learn Big-O and stop hacking your way through algorithms
by lern_too_spel on Thursday August 20, 2020 @06:48PM
(#24229918)
I'm saying that an O(n!) algorithm is not necessarily faster asymptotically than an O(n) algorithm and that saying it is shows a fundamental misunderstanding of the definition. This is regardless of time/space tradeoffs and large constants.
People who don't realize this end up here: https://accidentallyquadratic.tumblr.com/ :)