We know that we can do Perfect Hashing in expected linear time using a well-known two-level hash table approach. But what is the expected number of iterations that we do to construct the first level, only, of the hash table? The first level – the one where we are trying to find a hash function so that the squared lengths of the collision chains, $m_i^2$, in the buckets on the first level in linear.
I know how to prove that the expected number of iterations is constant for the construction of the second level, where we have $m_i^2$ places for $m_i$ elements but I'm not sure about the first level only.