# Deterministic dynamic dictionary on a small universe

We want to maintain a dictionary of $$m$$ elements with insert/delete and lookup in the word RAM model. Assume $$m=O(n)$$ at all times, so there can't be too many inserts without deletions. The universe has size $$\{0,\ldots,n^c-1\}$$ for some constant $$c$$.

How fast can we support these operations deterministically (in either worst case or amortized time) if we are restricted to $$O(n)$$ space? How about $$O(n \mathop{\mathrm{polylog}} n)$$ space?

A few simple observations:

• When $$c=1$$, an array of size $$n$$ support all operations in worst time $$O(1)$$.

• It's not hard to come up with a $$O(n^{1+\epsilon})$$ space data structure so all queries can be done in $$O(\frac{1}{\epsilon})$$ worst case time for any $$\epsilon>0$$.

• We can implement all operations in worst time $$O\left(\frac{(\log \log n)^2}{\log \log \log n}\right)$$ with $$O(m)$$ space using exponential tree.[1]

To clarify, I'm looking for dictionaries with space requirement as a function of the size of the universe, and not the number of elements in the dictionary.

If randomness is allowed, you can get space $B + o(B)$ and time $O(1)$ (worst-case, with high probability), where $B$ is $\lg {U \choose n}$, which is the lower bound on how much space you need using any representation: Arbitman et al., " Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation".
• They frequently have size $O(n \lg m)$. Do you want the space to not include any factor of $n$? – jbapple Dec 12 '13 at 16:42
• Sorry, that's supposed to be $O(n \lg U)$. – jbapple Dec 12 '13 at 16:51
• Yes, I like space of the form $O(U^{1/c})$ (and assume the dictionary never holds more than $U^{1/c}$ elements). The hope is that a relaxed bound can speed up the operations. – Chao Xu Dec 12 '13 at 16:58