State of the art low memory arbitrary-domain PRP?
Okay, here's the algorithm for "a fixed security level of 2128":

If ​ n ≤ 2^(2^128) ​ then sometimes-recurse shuffle with 128 bits of security.

If ​ 2^(2^128) &lt; n ​ then encryption just outputs the

plaintext and decryption just outputs the ciphertext.

The identity function can trivially be computed in O(1) space, so that algorithm

also uses only O(1) space. ​ (That's why, for true asymptotic analysis, one must

usually  assume some relation between n and the security parameter.)