Hashtable packing can be solved in O(n) space: just try out all possible combinations of offsets. To improve on this with square-root-of-time space, you would n

Hashtable packing can be solved in O(n) space: just try out all possible combinations of offsets. To improve on this with square-root-of-time space, you would need an algorithm that takes o(n²) time, but since hashtable packing is NP-complete, the existence of such an algorithm would imply P = NP.