CODEWITHSUNDEEP
mathcomputer-sciencebig-o
Tony The Lion
Tony The Lion

Reputation: 63250

Asymptotic complexity constant, why the constant?

Big oh notation says that all g(n) are an element c.f(n), O(g(n)) for some constant c.

I have always wondered and never really understood why we need this arbitrary constant to multiply with the bounding function f(n) to get our bounds?

Also how does one decide what number this constant should be?

Upvotes: 1

Views: 215

Answers (2)

Victor Sorokin
Victor Sorokin

Reputation: 12006

Consider function

f(n) = 4 * n

Doesn't it make sense to call this function O(n) since it grows "as fast" as g(n) = n. But without constant in definition of O you can't find n0 such as that for all n > n0, f(n) <= n. That's why you need constant, and indeed from condition,

4 * n <= c * n for all n > n0

you can get n0 == 0, c == 4.

Upvotes: 0

Jack
Jack

Reputation: 133609

The constant itself doesn't characterize the limiting behavior of the f(n) compared to g(n).

It is used for the mathematical definition, which enforces the existence of a constant M such that

alt text

If such a constant exists then you can state that f(x) is an O(g(x)), and this is the usual notation when analyzing algorithms, you just don't care about which is the constant but just the complexity of operations itself. The constant is able make that disequation correct by ensuring that M|g(x)| is an upper bound of f(x).

How to find that constant depends on f(x) and g(x) and it is the mathematical point that must be proved to ensure that f(x) has a g(x) big-o so there's not a general rule. Look at this example.

Upvotes: 3

Related Questions