# What is the average search complexity of perfect hashing?

The lookup time in perfect hash-tables is $O(1)$ in the worst case. Does that simply mean that the average should be $\leq O(1)$?

• Note that lookup in hashtables is rarely in $O(1)$. See here and here.
– Raphael
Jul 5 '12 at 7:00

Yes, but in complexity theory, $≤O(1)$ only means $O(1)$ i.e. constant time.

Given any set $X \subseteq \mathbb{R}$, you have

$\qquad \displaystyle \min X\ \leq\ \frac{1}{|X|}\sum_{x \in X} x\ \leq\ \max X$.

Therefore, average runtime is always bounded above by worst-case runtime. Denoting an asymptotic upper bound by "$\leq O(f)$" is abuse of notation, but will be understood.

To be more precise, you should say: upper bounds of worst-case runtime are upper bounds on average-case runtime, that is

$\qquad \displaystyle T_{\text{wc}} \in O(f) \ \implies\ T_{\text{ac}} \in O(f)$.

The reverse does not hold, that is lower bounds on the worst-case runtime do not carry over:

$\qquad \displaystyle T_{\text{wc}} \in \Omega(f) \quad\not\hspace{-.75em}\implies\ T_{\text{ac}} \in \Omega(f)$;

a well-known example for this is Quicksort. Of course, bounds can be transfered from average-case to worst-case in the opposite way.

You have to be careful, however, if the worst-case upper bound is an amortised one. Then, a certain sequence of operations is assumed, whereas average-case bounds assume a certain input distribution (often uniform). The two are not necessarily comparable, so amortised upper bounds do not necessarily bound the average case.

In algorithm complexity analysis theory, O(1) means the algorithm computes the answer independently of the number of elements -- for the particular case of a perfect hash algorithm, the "number of elements" is relative to the possible keys it may be presented to.

However, such algorithms still have a complexity in regard to the length of the key present. So, the worst case will happen for the bigger key -- but will still be O(1) in regard to the number of possible keys. Conversely, the best case will happen for the smaller key, but will still be O(1).

So, both worst and best cases will have O(1) complexity, even if their computation time is (slightly) different.

• Running time is usually described in terms of the length of the input, not the "number of elements". Dec 8 '18 at 22:06