Let us define a "root universal family" as a family of hash function which for every two items $k_i,k_j$ the probability $P(h(k_i)=h(k_j)) \le \frac{1}{\sqrt m}$ where $m$ is the size of the table.
Now, let us have $|U| = n$ - (the size of the given universe, note that it is perfect hash).
Define an efficient perfect hash algorithm, for which the total sizes of the tables is $\le O(n^2)$.
Now, we note that if we have a table of size $n^2$, then the expected number of collision of a random hash function from that family is $\le \frac{n}{2}$. This is because:
$$\mathbb E[\text{number of collisions}] = \sum_{\{k_i,k_j\} \subset U, k_i\ne k_j}P(h(k_i)=h(k_j)) \le \frac{\binom{n}{2}}{\sqrt {n^2}} \le \frac{n}{2}$$
So, we define the "first-level" hash table to be of size $n^2$. The expected number of hash function we need to draw in order to have less than $n$ collisions is $2$ (since it is a geometric variable).
Now, this is where I get stuck:
After a hash family that satisfies less then $n$ collisions is chosen, for each table that has items colliding, we make a "second-level" table of size $|\text{number of collisions in table}|^4$. (It is easy to prove that in order to get no collisions when the size is $x^4$ we need again two draws for the second function.
The problem I having is showing that all the "second-level" tables + the "first-level" tables are $O(n^2)$ of total size. Would like help in proving that, Thanks!
