> (where the input is an array that is stored in memory)? If the input is an array that is stored in a piece of real-world memory, then the only possible compl

> (where the input is an array that is stored in memory)? If the input is an array that is stored in a piece of real-world memory, then the only possible complexity is O(1). It's just how big-O works. Big-O notation is an abstraction that is much much closer to mathematics than to engineering. > this big-O notation is pretending to have some real-world usefulness... Big-O notation is not a person so I'm not sure whether it can pretend something. CS professors might exaggerate big-O notation's real-world usefulness so their students don't fall asleep too fast. > fictional Theoretical. Just like the other theoretical ideas, at best big-O notation gives some vague insights that help people solve real problems. It gives a very rough feeling about whether an algorithm is fast or not. By the way, Turing machine is in this category as well.