Why doesn't the additive constant in Big-O notation matter?

Question

In definition of Big-O notation we care only about C coefficient:

f(n) ≤ Cg(n) for all n ≥ k

Why don't we care about A as well:

f(n) ≤ Cg(n) + A for all n ≥ k

Answer 1

Big-O notation is about what happens as the data gets larger. In other words, it is a limit as n --> infinity.

As n gets large, A remains the same. So it gets smaller and smaller in comparison. On the other hand, g(n) (presumably) gets bigger and bigger, so its contribution increases more and more.

Answer 2

There are really two cases to consider here. For starters, imagine that your function g(n) has the property that g(n) ≥ 1 for all "sufficiently large" choices of n. In that case, if you know that

f(n) ≥ cg(n) + A,

then you also know that

f(n) ≥ cg(n) + Ag(n),

so

f(n) ≥ (c + A)g(n).

In other words, if your function g is always at least one, then bounding f(n) by something of the form cg(n) + A is equivalent to bounding it with something of the form c'g(n) for some new constant c'. In that sense, adding some extra flexibility into the definition of big-O notation, at least in this case, wouldn't make a difference.

In the context of the analysis of algorithms, pretty much every function g(n) you might bound something with will be at least one, and so we can "munch up" that extra additive term by choosing a larger multiple of g.

However, big-O notation is also used in many cases to bound functions that decrease as n increases. For example, we might say that the probability that some algorithm gives back the right answer is O(1 / n), where the function 1/n drops to 0 as a function of n. In this case, we use big-O notation to talk about how fast the function drops off. If the success probability is O(1 / n²), for example, that's a better guarantee than the earlier O(1 / n) success probability, assuming n gets sufficiently large. In that case, allowing for additive terms in the definition of big-O notation would actually break things. For example, intuitively, the function 1 / n² drops to 0 faster than the function 1 / n, and using the formal definition of big-O notation you can see this because 1 / n² ≤ 1 / n for all n ≥ 1. However, with your modified definition of big-O notation, we could also say that 1 / n = O(1 / n²), since

1 / n ≤ 1 / n² + 1 for all n ≥ 1,

which is true only because the additive 1 term bounds the 1/n term, not the 1/n² we might have been initially interested in.

So the long answer to your question is "the definition you proposed above is equivalent to the regular definition of big-O if we only restrict ourselves to the case where g(n) doesn't drop to zero as a function of n, and in the case where g(n) does drop the zero as a function of n your new definition isn't particularly useful."

Answer 3

A is constant in this case, thus it will not affect much the complexity when the size of the problem grows very much.

When you have a cost of 1 million, you do not care if you add up a constant factor of 100 for example. You care for how this 1 million grows (resulting from Cg(n)); whether it becomes 2 millions for example if the size of the problem grows a bit. However, your constant will still be 100, so it doesn't really affect the overall complexity.