Abstract
This entry provides Landau symbols to describe and reason about the asymptotic growth of functions for sufficiently large inputs. A number of simplification procedures are provided for additional convenience: cancelling of dominated terms in sums under a Landau symbol, cancelling of common factors in products, and a decision procedure for Landau expressions containing products of powers of functions like x, ln(x), ln(ln(x)) etc.
License
Topics
Session Landau_Symbols
Used by
- The Error Function
- Dirichlet L-Functions and Dirichlet’s Theorem
- Dirichlet Series
- CryptHOL
- Expected Shape of Random Binary Search Trees
- Lower bound on comparison-based sorting algorithms
- The number of comparisons in QuickSort
- The Euler–MacLaurin Formula
- Stirling’s formula
- Catalan Numbers
- The Akra-Bazzi theorem and the Master theorem