I'm reading Quantum Computing: An Applied Approach, by Hidary. Chapter 8.2 (p104) says:
While it is true that Deutsch-Jozsa demonstrates an advantage of quantum over classical computing, if we allow for a small error rate, then the advantage disappears: both classical and quantum approaches are in the order of $O(1)$ time complexity.
How is it possible that classical DJ can work with a single oracle query? I am probably missing something deep about the meaning of "a small error rate". An intuitive explanation would be preferred over a heavy-math one, if possible.