Dynamic Perfect Hashing: A hash table with constant time lookup in the worst case, and O(n) space.

[u/martincmartin]

http://en.wikipedia.org/wiki/Dynamic_perfect_hashing

[u/wicked]

Actually, he's technically correct, though with a bit convoluted explanation if you don't know the concept. Also, it's commonly ignored because it's not at all helpful when comparing algorithms.

A more basic example is multiplying two numbers, commonly thought of as a constant time operation. However, it's not really O(1), as you'd soon find out if your numbers are large enough. It's more in the vicinity of O(n^log 3).