News for hackers. Stuff that matters.
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.