Asymptotic analysis

In <a href="/facts/Mathematical_analysis/XXeR26Ih">mathematical analysis</a>, asymptotic analysis, also known as asymptotics, is a method of describing <a href="/facts/Limit_(mathematics)/j8JBhj4e">limiting</a> 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 <a href="/facts/Prime_number_theorem/3KA9egls">prime number theorem</a>. Let π(x) denote the <a href="/facts/Prime-counting_function/Dk1xJzsA">prime-counting function</a> (which is not directly related to the constant <a href="/facts/Pi/vC0UBj1q">pi</a>), i.e. π(x) is the number of <a href="/facts/Prime_number/L20FLkgn">prime numbers</a> that are less than or equal to x. Then the theorem states that

π
        (
        x
        )
        ∼
        
          
            x
            
              ln
              ⁡
              x
            
          
        
        .
      
    
    {\displaystyle \pi (x)\sim {\frac {x}{\ln x}}.}

Asymptotic analysis is commonly used in <a href="/facts/Computer_science/lN3pEyPz">computer science</a> as part of the <a href="/facts/Analysis_of_algorithms/pStoBgBn">analysis of algorithms</a> and is often expressed there in terms of <a href="/facts/Big_O_notation/weFFjSWg">big O notation</a>.

Asymptotic analysis open-in-new

Asymptotic analysis