I'm fond of this brain-expander, in spirit of TFA: "Did you know travelling salesperson is O(N) on a large class of graphs?"

Another insight: I regularly find that clever O(logn) solutions are just obliterated by a few mostly-branch-free O(N) pre-passes followed by a problem that computers enjoy, like contiguous memory access and vector operations.