Skip to main content
2 of 2
fixes math layout to LaTeX
Raphael
  • 72.9k
  • 30
  • 181
  • 393

A perfect hash function will result in $\cal{O}(1)$ worst case lookup.

Moreover, if the maximum number of collisions possible is $\cal{O}(1)$, then hash table lookup can be said to be $\cal{O}(1)$ in the worst case. If the expected number of collisions is $\cal{O}(1)$, then the hash table lookup can be said to be $\cal{O}(1)$ in the average case.