r/algorithms • u/Kendama_Llama • 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?
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
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.
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).