homepage

Logged In: YES 
user_id=341410
"Saving the value makes dict lookup of tuples an operation
with an amortized cost of O(1)."
This is an incorrect statement in regards to caching. The
initial hashing costs whatever it takes to hash the tuple (
Omega(len(tuple)) time at least), but subsequent hashes cost
O(1). Ammortized over 2 hashes is still Omega(len(tuple))
per hash, not O(1) as you stated. In order for
ammortization to help the bounds, you would need to hash the
tuple Omega(len(tuple)) times (assuming the contents of the
tuple are hasable in O(1) time without ammortization), at
which point you would get O(1) ammortization.