math - Asymptotic complexity constant, why the constant? -


big oh notation says g(n) element c.f(n), o(g(n)) constant c.

i have wondered , never understood why need arbitrary constant multiply bounding function f(n) our bounds?

also how 1 decide number constant should be?

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

it used mathematical definition, enforces existence of constant m such that

alt text

if such constant exists can state f(x) o(g(x)), , usual notation when analyzing algorithms, don't care constant complexity of operations itself. constant able make disequation correct ensuring m|g(x)| upper bound of f(x).

how find constant depends on f(x) , g(x) , mathematical point must proved ensure f(x) has g(x) big-o there's not general rule. @ this example.


Comments