For efficiency, it is desirable for the size u of the universe be bounded in the number of elements n stored in the data structure.
However, under some restrictions, \Omega(\log^2 n) lower bounds have been found on the performance of insertion in solutions of the list-labeling problem with linear universes[REF] whereas we will see below that a solution with a polynomial universe can perform insertions in O(\log n) time.