3 ms·
It's a good check on yourself though. Even if you don't know formal big-O, knowing that something that's O(n) will be faster than O(n!) is pretty important. Pe
by xxpor 6y ago
It's a good check on yourself though. Even if you don't know formal big-O, knowing that something that's O(n) will be faster than O(n!) is pretty important.
People who don't realize this end up here: https://accidentallyquadratic.tumblr.com/ https://accidentallyquadratic.tumblr.com/ :)
- quickthrower2 6y agoThe 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.
- taeric 6y agoAmusingly, 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.)
- lern_too_spel 6y agoI 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.
- xxpor 6y agoSure, 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.
- lern_too_spel 6y agoI'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.