0
$\begingroup$

I do not have much experience in mathematics but I would really like to grasp Big-O notation on its mathematical level. I already read What does the "big O complexity" of a function mean? from references, but I still do not understand (even graphically), what does it mean when we say:

T(n) = O(f(n)) if and only if there are constants c and g such that: T(n) <= c*f(n), where n>=g

Specifically, we say that T(n) is upper bounded by c*f(n). What does that actually mean and why does it matter? Does it have to do with eliminating constant factors and low-ordered terms?

Sorry if question is kind of confusing, and thanks for the help!

$\endgroup$
  • $\begingroup$ Graphically: the bounded function is not curved stronger in direction of +infinity than the bound is. $\endgroup$ – greybeard Nov 27 '19 at 4:01
2
$\begingroup$

Try it like this: "we can pick a constant $C$ such that, for sufficiently large $n$, $T(n)$ will always be less than $Cf(n)$".

Intuitively, this does indeed mean that lower-order terms and constant factors don't matter. Because lower-order terms stop mattering once $x$ gets sufficiently large, and constant factors can be cancelled out by an appropriate choice of $C$. If $T(n) = n^3 + 2019n^2 + 99999n + 10^{10}$, for example, that will still eventually be dominated by $Cn^3$, as long as $C > 1$ and $n$ is large enough—the $n^3$ term in that expression will eventually outweigh everything else. So we say that $T(n) \in O(n^3)$. (Some people use an equals sign instead; the meaning is the same.)

The "sufficiently large $n$", by the way, is why it's called "asymptotic" complexity: we only care about what happens as $n$ goes toward infinity, not what happens for "small" values.

$\endgroup$
  • $\begingroup$ Thank you. I think I've grasped better intuition now of this concept. $\endgroup$ – Stefan Radonjic Nov 27 '19 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.