Re:When your data doesn’t fit in memory: the basic techniques
by nothrabannosir on Tuesday November 12, 2019 @05:01AM
(#21512918)
To be fair he did say O(1), and qualified the O(log N) with both parentheses and “to be really precise”. If you can’t be precise about the definition of O on HN, then where? (which, “to be really precise”, is a polynomial time tape based Turing machine, not a modern RAM machine with log N words. It’s pointless, but fun to remember :) )
[ Parent
| on HN ]
Re:When your data doesn’t fit in memory: the basic techniques
by lorenzhs on Tuesday November 12, 2019 @05:06AM
(#21512945)
No no no! Big O has nothing to do with Turing machines at all! You can, of course, express the number of steps a single-tape deterministic Turing machine needs to solve some problem using Big O notation. But you can just as well express the number of Qubits that a quantum computer needs to solve some other problem in Big O notation. It has nothing to do with the quantity being measured. Are you perhaps mixing up the definition of complexity classes such as P and NP with Big O notation?
First you need to settle on a model. Then you can express time, space, or some other quantity in that model using Big O notation.
Arguably, I've found that HN is one of the worst places to be precise about Big O notation. Everyone here seems to think they know what it is, only to lay bare their misconceptions about it a second later.