This is a pet peeve of mine in interviews when asked what the big O of hash table lookup is and I say "you're probably looking for O(1), but it's really O(log n

This is a pet peeve of mine in interviews when asked what the big O of hash table lookup is and I say "you're probably looking for O(1), but it's really O(log n). The assumption is that you can hash a word sized quantity and access the corresponding memory in constant time, but the whole point of Big O is asymptotic complexity, and just taking the hash of N bits is going to take O(n) time. Now I get called a pedant for this, but really log n time is for most purposes close enough to constant time to be negligible for practical purposes. Log n factors are unlikely to determine whether an algorithm is feasible, as the constant factor is usually way more significant.