News for hackers. Stuff that matters.
Re:Why databases use ordered indexes but programming uses ha... by jhanschoo on Tuesday December 10, 2019 @02:13AM (#21750364)
Indeed, in the TM model hash table lookups are necessarily Omega(n) in the length of data stored.

The model of computation used in these analyses and interview questions I'd say is a random-access infinite register machine of infinite size (and constant arithmetic), which is more powerful than a TM (and siblings) in complexity analyses.

Of course, they are useless for analyzing complexity classes of computational problems, but you can use them to talk about the complexity of computer algorithms.

There are no comments on this comment yet.