Re:Why databases use ordered indexes but programming uses ha...
by jhanschoo on Tuesday December 10, 2019 @02:18AM
(#21750381)
Yes, it is, but the question is how do you make this notion of "realistic" formal and rigorous. The usual model for complexity analyses, the TM, can't do constant-time arithmetic. So we're interested in a more powerful model.
I'd proposed a model in a sibling comment that seems to be the one most people use for analyzing algorithms.
Re:Why databases use ordered indexes but programming uses ha...
by johncolanduoni on Tuesday December 10, 2019 @04:40AM
(#21751044)
A Turing machine can do constant-time arithmetric (or more simply, constant-time bound arithmetic) for operands of bounded size, as was suggested above.
So saying such a structure has O(1) asymptotic access time is not perfectly true in a mathematical sense, for unrealistic numbers. But it's certainly realistic.