Earlier quoted context omitted.
Given that computer scientists use the word "efficiently" to mean "in polynomial time", I'm not too upset at using "quickly" to mean the same.
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 cer…
> "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