[corysama]

Sure. But, in practice it’s never a debate between O(1) vs. a O(large n). It’s always either a heavy O(1) vs. a light O(small n) —-hash vs. linear search. Or, a heavy O(large n) vs. a light O(large n log n) —-hash everything vs. sort everything. In both cases, the second option usually wins.