And any operation that takes n bits as input can be trivially turned into an O(1) time and O(2^n) space algorithm through tabulation.

Assuming you ignore or amortize the time necessary to create the table in the first place, of course.

This is the basis for rainbow tables: precomputed tables for mapping hashes to passwords, with a space-saving “hash chaining” trick to effect a constant factor reduction in table size. Such tables are the reason why passwords must be hashed with a unique salt when stored in a database.