I am looking for a pairing function with linear time complexity.
I found
- one in Steven Pigeon's thesis (p 115, §5.3.6.3) described in English on MathOverflow that works by bit interleaving.
- another from Regan's 1992 paper (p 289, last paragraph) that works by bit concatenation based on a state machine.
The one from Pigeon seems $O(1)$ in space and $O(n)$ in time to me, assuming fixed-length datatypes (int64). Space $O(1)$ would derive from the fact that
$bitlength(z) = 2*max(bitlength(x),bitlength(y))$
$O(n)$ time seems to trivially derive from the absence of any operation apart from bit interleaving, which is $O(1)$ for each pair of bits.
What bugs me is that in Regan (1992), the algorithm is more involved but claims identical time and space complexity. I guess I am misunderstanding something.
Is the Pigeon function really $O(n)$ in time? If the problem of integer pairing has such a simple solution, how come Cantor's and the Rosenberg-Strong pairing functions are cited so widely while having inferior performance characteristics?
