Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Asymptotic analysis
Summary
In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior.
As an illustration, suppose that we are interested in the properties of a function f (n) as n becomes very large. If f(n) = n2 + 3n, then as n becomes very large, the term 3n becomes insignificant compared to n2. The function f(n) is said to be "asymptotically equivalent to n2, as n → ∞". This is often written symbolically as f (n) ~ n2, which is read as "f(n) is asymptotic to n2".
An example of an important asymptotic result is the prime number theorem. Let π(x) denote the prime-counting function (which is not directly related to the constant pi), i.e. π(x) is the number of prime numbers that are less than or equal to x. Then the theorem states that
Asymptotic analysis is commonly used in computer science as part of the analysis of algorithms and is often expressed there in terms of big O notation.
Formally, given functions f (x) and g(x), we define a binary relation
if and only if
The symbol ~ is the tilde. The relation is an equivalence relation on the set of functions of x; the functions f and g are said to be asymptotically equivalent. The domain of f and g can be any set for which the limit is defined: e.g. real numbers, complex numbers, positive integers.
The same notation is also used for other ways of passing to a limit: e.g. x → 0, x ↓ 0, → 0. The way of passing to the limit is often not stated explicitly, if it is clear from the context.
Although the above definition is common in the literature, it is problematic if g(x) is zero infinitely often as x goes to the limiting value. For that reason, some authors use an alternative definition. The alternative definition, in little-o notation, is that f ~ g if and only if
This definition is equivalent to the prior definition if g(x) is not zero in some neighbourhood of the limiting value.
If and , then, under some mild conditions, the following hold:
for every real r
if
Such properties allow asymptotically-equivalent functions to be freely exchanged in many algebraic expressions.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.