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)$?
Yes, but in complexity theory, $≤O(1)$ only means $O(1)$ i.e. constant time.