4 ms·
A hash table lookup is O(n), where n is the number of elements in the table. They have amortized constant time lookup (i.e. constant time in the average case).
by timr 14y ago
A hash table lookup is O(n), where n is the number of elements in the table. They have amortized constant time lookup (i.e. constant time in the average case).
- shrughes 14y agoOr it's O(log n). Depends on how collisions are handled.
- timr 14y agoIf you use a balanced tree instead of chaining or probing, sure. But, of course, nobody ever does that in practice, because the complexity isn't justified by the theoretical gains. Point was, worst-case time complexity isn't constant. I'd be happy to see more people get that right in interviews.
- haberman 14y agoHash tables, in general, have average constant time lookup. Only some hash tables have amortized constant time lookup. An amortized bound is a bound on the total cost of a sequence of operations. Loosely speaking, it guarantees that you can't keep hitting the worst case indefinitely. An average bound is averaged over all possible inputs, but doesn't protect you against hitting the worst case over and over.
- deleted 14y ago[deleted]