I think a simplified explanation is that, assuming your hash function is ideal (can be assumed to be random, except for being deterministic), you end up buildin

I think a simplified explanation is that, assuming your hash function is ideal (can be assumed to be random, except for being deterministic), you end up building a treap, minus the treap's restriction on the in-order traversal of keys and restriction on the number of children. The height of a treap is O(log N), so your solution is expected to be within a constant factor of an optimal solution. [0] https://en.wikipedia.org/wiki/Treap https://en.wikipedia.org/wiki/Treap