2
$\begingroup$

I am looking for a pairing function with linear time complexity.

I found

  1. one in Steven Pigeon's thesis (p 115, §5.3.6.3) described in English on MathOverflow that works by bit interleaving.
  2. 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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.