2

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)?

Community
  • 1
  • 1
George Geschwend
  • 183
  • 2
  • 9

2 Answers2

4

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

limn → ∞ 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 n0 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.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
0

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

Vatine
  • 20,782
  • 4
  • 54
  • 70