Why databases use ordered indexes but programming uses hash tables
Nit-pick / pet-peeve regarding Big O notation!<p>> Hash tables provide constant time O(1) access for single values, while trees provide logarithmic time O(log n) access. For single value lookups, this means hash tables are faster,<p>> for small n, the hash table is better, but for large n, the cost of that rare scan dominates, and the tree is better<p>The Big O notation describes how the number of operations scales as the size of the input tends to infinity: the asymptotic complexity. This means that an O(1) algorithm can include some fixed number of operations, even enough to add _years_ onto the runtime, and still be classed as O(1).<p>Essentially I don’t think it’s really enough to consider the asymptotic complexity of algorithms to compare practical runtimes. You need to know what the smaller-order / constant terms are.