Re:P≠NP proof update
by carbocation on Sunday August 15, 2010 @08:25PM
(#1606358)
Despite being correct in the narrow sense, you nevertheless end up being wrong in a broader, more useful sense.
I do not disagree with the definition. But you shouldn't rigidly focus on the definition without considering the utility of the notation, and the purpose of the discussion.
Big O notation describes the asymptotic behavior of a function when the argument N being passed to it approaches infinity. This is why it is also known as asymptotic notation.
Now, since this thread is about practical consequence, there is a severe problem with glibly saying that n * 999^999^999^999^999 will ever remotely resemble n from a practical standpoint. You'll never be able to compute f(1), much less a value of n large enough to be limiting.
At any rate, it looks like we both agree that O notation doesn't help you here. My fault for bringing it up.
The definition of O(n) is: f is in O(n) so long as |f(n)| <= M * |n| for some constant M.
Likewise, the definition of O(n * c) would be: f is in O(n * c) so long as |f(n)| <= M' * |n * c| for some constant M'.
As you can see, any function f which is in O(n * c) is also in O(n), and vice versa.
The entire point of complexity classes is to describe asymptotic behavior. If you want to describe something other than asymptotic behavior, find a different tool.