Asymptotic

Asymptotic describes the limiting behavior of a function or sequence as its input grows without bound, approaches a specified value, or tends to zero in a small parameter. In practice, statements about asymptotics compare functions in the limit, often by expressing that one quantity is approximately equal to another up to a negligible error when the variable becomes large.

Several standard notations express these ideas. f(x) = O(g(x)) as x → ∞ means that, beyond some point, |f(x)| is bounded by a constant multiple of |g(x)|. The little-o notation f(x) = o(g(x)) means the ratio f(x)/g(x) tends to 0. Asymptotic equality f(x) ~ g(x) means lim f(x)/g(x) = 1 (provided g(x) ≠ 0). The symbol Θ(g(x)) or Theta indicates that f and g grow at the same rate, i.e., f = O(g) and g = O(f).

Applications include asymptotic analysis in mathematics and computer science, where one characterizes the growth rate of algorithms or the behavior of functions for large arguments. It also encompasses asymptotic expansions, where a function is approximated by a leading term plus smaller corrections in a limit.

Examples: f(n) = n^2 + n satisfies f(n) ~ n^2 as n → ∞, and f(n) = Θ(n^2). Also log n = o(n^a) for any a > 0, while e^n dominates any polynomial, so n^k = o(e^n).