[nawitus]

>All big-O has an implied "+C"

Can you state this in a mathematically precise notation?

>Where is the confusion?

The confusion comes from stateents like 'O(n)+C = O(n)', which are actually false. O(n)+C and O(n) are different sets. If a function belongs to the latter set, it also belongs to the former, but that doesn't mean they're equal.

Using the equal sign here is "abuse of notation". 'O(n)+C = O(n)' would seem to implicate that C=0, but that's untrue. C is a constant which can be non-zero. Therefore the whole statement doesn't really make sense unless we assign a new definition to the equal sign.

Using set notation solves all the confusion.

'Implied +C' is pretty much nonsense. There are an infinite number of different sets that a single function belongs to. Just because f(x) belongs to O(n) and therefore to O(n)+C doesn't mean that 'big-O implies +C'. 'big-O' doesn't imply anything like that. '+C' is just a special case, and there's an infinite number of extra 'implies'.

[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.

[dragonwriter]

> O(n)+C and O(n) are different sets.

Yes, and no. O(n) isn't a set until you specify the limit that goes with it; for some limits O(n) is different from O(n)+C -- the latter of which is equivalent to O(n+C). However, in CS, O(n) with no specified limit refers by convention to the set O(n) as n->infinity, and O(n) as n->infinity is equal to O(n+C) as n->infinity, because the limit as n->infinity of n is equal to the limit as n->infinity of n+C.

[jlarocco]

> Can you state this in a mathematically precise notation?

Big-O isn't meant to be precise. The entire point is to roughly describe algorithm behavior.

> 'Implied +C' is pretty much nonsense.

Implied +C is built in to the definition of big-O notation. As n increases towards infinity the influence of C becomes negligible, so it's left off. Read the first chapter of any algorithms book.