4 ms·
Idk, I majored in CS and I don't use the term efficient or quick to imply relative asymptotic time complexity. Consider for example a randomized quicksort (O(n
by skate22 8y ago
Idk, I majored in CS and I don't use the term efficient or quick to imply relative asymptotic time complexity.
Consider for example a randomized quicksort (O(n^2) worst case) is often faster than say mergesort (O(nlog(n)) worst case)) for small lists due to reduced overhead. I know these are both polynomial, but relatively speaking, randomized quicksort can be more efficient & quick.
In the real world we can make certain assumptions about our problem domain, where the most 'efficient' solution for your business problem may not have the smallest asymptotic time complexity.
Maybe it's fair to assume everyone reading this article knows what the auther means & i'm just being that guy, but I still don't like ambiguity lol
- doubleunplussed 8y agoIt's used when talking about the extended Church-Turing thesis [1]: > "A probabilistic Turing machine can efficiently simulate any realistic model of computation." The word 'efficiently' here means up to polynomial-time reductions. Real-world efficiency doesn't necessarily factor into what theoretical computer scientists are interested in. [1] https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis