In the context of Big O notation, what does asymptotic or asymptotically mean?

Question

I am trying to understand the words asymptotic and asymptotically. In other words, what do we really mean by a growth rate f(x) being asymptotically greater than, less than, greater than or equal to, less than or equal to g(x) what does asymptotically really mean? I am not looking for a rehash of the question: "What is big O, big Theta and big Omega notation?"; just the meaning of the words asymptotic and asymptotically in this context.

Example:

"f(x) = O(g(x)) (big-oh) means that the growth rate of f(x) is asymptotically less than or equal to the growth rate of g(x)."

The above was taken from this Stack Overflow page: What is the difference between Θ(n) and O(n)?

Answer 1

Mathematically, you can think of the statements f(n) = O(g(n)) and f(n) = Θ(g(n)) as ways of reasoning about the behavior of

lim_{n → ∞} f(n)/g(n)

Specifically, if f(n) = O(g(n)), then this limit exists and is some finite value, and if f(n) = Θ(g(n)), then this limit exists and its value is nonzero and not infinite. In this sense, "asymptotically" means the same thing as the term "asymptotically" from calculus - we're reasoning about the behavior of some quantity in the limit.

Formally, the definition of big-O notation involves finding constants c and n₀ with various properties. These properties turn out to be exactly the properties necessary to make the above limit converge to a value under the formal definition of a limit to infinity. It's not often taught this way, but this is mathematically equivalent.

Answer 2

It means that if you have 'f(x) = O(g(x))', there is an x (x_n) such that for all values of x such that 'x >= x_n', f(x) <= C * g(x) (for a constant C larger than 0)'.