**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 GraphSearch.

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
\pi(x)\sim\frac{x}{\ln x}.
Asymptotic analysis is commonly used in computer science as part of the analysis of algorithms and is o

Official source

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.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related people (10)

Related courses (36)

PHYS-432: Quantum field theory II

The goal of the course is to introduce relativistic quantum field theory as the conceptual and mathematical framework describing fundamental interactions.

MATH-442: Statistical theory

The course aims at developing certain key aspects of the theory of statistics, providing a common general framework for statistical methodology. While the main emphasis will be on the mathematical aspects of statistics, an effort will be made to balance rigor and intuition.

MATH-301: Ordinary differential equations

Le cours donne une introduction à la théorie des EDO, y compris existence de solutions locales/globales, comportement asymptotique, étude de la stabilité de points stationnaires et applications, en particulier aux systèmes dynamiques et en biologie.

Related publications (100)

Loading

Loading

Loading

Related lectures (78)

Related units (9)

Related concepts (24)

Big O notation

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notatio

Combinatorics

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many

Gamma function

In mathematics, the gamma function (represented by Γ, the capital letter gamma from the Greek alphabet) is one commonly used extension of the factorial function to complex numbers. The gamma functio

We study in this thesis the asymptotic behavior of optimal paths on a random graph model, the configuration model, for which we assign continuous random positive weights on its edges.
We start by describing the asymptotic behavior of the diameter and the flooding time on the graph for a set of light-tailed edge-weights, and we prove that it is the largest class of densities for which these precise asymptotic expressions for the diameter/flooding time hold.
We then show how the weighted optimal path can be constructed using a particular positive recurrent Markov chain.
We finally study, in the last chapter, the noise sensitivity of the model by replacing every edge-weight independently by a new realization of the same distribution, with probability epsilon. We show that the optimal paths between two vertices before and after this modification are asymptotically ''independent'' conditioning on the graph, as the number of vertices tends to infinity.

We prove an asymptotic formula for the second moment of a product of two Dirichlet L-functions on the critical line, which has a power saving in the error term and which is uniform with respect to the involved Dirichlet characters. As special cases we give uniform asymptotic formulae for the fourth moment of individual Dirichlet L-functions and for the second moment of Dedekind zeta functions of quadratic number fields on the critical line.

2020We prove an asymptotic formula for the shifted convolution of the divisor functions d(k)(n) and d(n) with k >= 4, which is uniform in the shift parameter and which has a power saving error term, improving results obtained previously by Fouvry and Tenenbaum and, more recently, by Drappeau.