News for hackers. Stuff that matters.
Re:P≠NP proof update by jacobolus on Sunday August 15, 2010 @08:16PM (#1606341)
Wrong. O(n * c) = O(n).

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.

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.