r/algorithms • • Sep 25 '15

For practical computing purposes, every algorithm is O(1)?

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?

0 Upvotes

8 comments sorted by

17

u/R4_Unit Sep 25 '15

The comment is a bit oddly phrased, but all your professor means is that the computer sitting on your desk only has a finite amount of memory, thus any program on our had bounded memory use. Similarly, any computation is bounded in time by the life of the computer, this both are O(1).

2

u/grencez Sep 25 '15

any computation is bounded in time by the life of the computer

Yeah, maybe that is a better way of thinking about it. Usually the result of constant time is derived from the fact that the number of system states/configurations is finite. But realistically, the algorithm would behave incorrectly if it ran up against memory limits (e.g., crash, infinite loop, or return bad result). So at that point, we're not even running the algorithm that's being analyzed.

1

u/bobhyman4 Sep 28 '15

My old boss used to say "In the long run we're all dead anyway!"

5

u/flebron Sep 25 '15

What does "using the negation of the definition for Big O" mean? You likely misheard your professor.

9

u/LoveOfProfit Sep 25 '15 edited Sep 25 '15

...wat

If you make your data set very small, you can make the constant very large, and then that's kinda true. The issue is that Big O notation is literally talking about how an algorithm behaves as the data size approaches infinity. I guess his argument is probably that for practical computing purposes, data sets aren't infinite (memory limits) and so any growth order can be replaced with a constant.

To claim that every algorithm is O(1) on this basis though is bullshit. It misses the point of Big O notation.

4

u/flebron Sep 25 '15

Fixing the data size and then using "O" doesn't make sense, since "O" means "As the input size grows unbounded." If you've fixed it, it's not growing unbounded. You can pick one of the two, but not both at the same time.

4

u/LoveOfProfit Sep 25 '15

I'm aware. I pointed out that exact thing in my comment.

4

u/Ravek Sep 25 '15 edited Sep 25 '15

Like any big O analysis it depends on your computation model. Adding two integers is O(n) in the number of digits if you do it by hand, but it's also O(1) on any modern computer as long as they fit in 64 bits. Your assumptions matter.

Assuming your professor isn't nuts he's probably drawing from some sake-of-argument computation model. E.g. defining an operation on the order of the lifetime of a machine as constant time, any realistic program would run in constant time.