2
$\begingroup$

I am taking a course in algorithm analysis and the professor is arguing that using the negation of the definition for Big O, it can be argued that, for practical computing purposes, both the running time and the memory usage of every algorithm is O(1). How is this possible? How can it be proven?

$\endgroup$
6
$\begingroup$

Sure. Time and memory are both finite, thus $O(1)$. But that isn't a very interesting (useful) result. Complexity is studied precisely because we do care how much time (or memory, or whatever other measure is of interest) algorithms take as a function of the input (size), even if we aren't willing to wait "finite, but very large" time nor to equip the machine with "finite, but very large" memory. We'd want to have an idea of how long we have to wait, or how much memory is enough.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.