[anonymoushn]

http://en.wikipedia.org/wiki/Big_O_notation#Formal_definitio...

A function f(x) is a member of the set O(n) iff there is some M,x0 such that for all x>x0, |f(x)|<=Mn. This means functions like lg n, n+30, n+1e999, 1e999n + sqrt(n), sin(n), and 7 are all members of the set O(n).

It is difficult to give a formal proof that O(n) + C = O(n) because there isn't really a formal notion of what is meant by O(n) + C. To me, that looks like the result of adding a real constant to a set of functions. It is common to see people do algorithmic analysis and replace terms in a runtime with a set they belong to, in which case an expression like O(n) + C might appear, but what this means is just "some function that is in O(n) plus some constant," and it is simple to prove that the set of all functions that can be described in this way is equal to the set O(n). O(n) is closed under the operation of adding constants, and the "adding constants" operation is its own inverse.