当输入规模足够大，使得只有运行时间的增长量级有关时，我们要研究算法的渐进效率。

渐近记号

Θ记号

Θ记号渐近地给出一个函数的上界和下界。对一个给定的函数g(n)，用Θ(g(n))来表示以下函数的集合：

Ο记号

当只有一个渐近上界时，使用Ο记号。对于给定的函数g(n)，用Ο(g(n))（读作“大Og(n)”，有时仅读作“Og(n)”）来表示以下函数的集合：

Ω记号

Ω记号提供了渐近下界。对于给定的函数g(n)，用Ω(g(n))（读作“大Ωg(n)”，有时仅读作“Ωg(n)”）来表示以下函数的集合：

根据目前所看到的这些渐近记号的定义，容易证明以下重要定理：

o记号

由O记号提供的渐近上界可能是也可能不是紧确的。界2n² = O(n²)是渐近紧确的，但是界2n = O(n²)却不是。我们使用o记号来表示一个非渐近紧确的上界。形式化地定义o(g(n))（读作“小og(n)”）为以下集合：

例如，2n = o(n²)，但是2n² ≠ o(n²)

ω记号

ω记号与Ω记号的关系类似于o记号与O记号的关系。我们使用ω记号来表示一个非渐近紧确的下界。定义它的一种方式是：

或者形式化地定义它：

其他

本章中介绍的其他数学概念较为简单和常用，便不在此赘述。