I like to point out that hash tables are O(N) when people bring this up. Constant factors, average cases, and practical considerations matter a lot - it's not just nitpicking or semantics.