记号

定义

对一个给定的函数 g(n)，用 (g(n))来表示函数集合： = {：存在正常量 和 使得对所有 ，有 }。

解释

对任一个函数 f(n)，若存在正常数 ，，使当 n 充分大时，f(n) 能被夹在 和 中间，则 f(n) 属于集合 。因为 是一个集合，可以写成 “”，表示 f(n) 是 的元素。不过，通常写成 “”来表示相同的意思。

上图给出函数 f(n) 与 g(n) 的直观图示，其中 f(n) = 。对于所有位于 右边的 n 值，f(n) 的值落在 和 之间，换句话说，对所有的 n≥，f(n) 在一个常因子范围内与 g(n) 相等。我们说 g(n) 是 f(n) 的一个渐近紧确界。

的定义需要每个成员 都是渐近非负，也就是说当 n 足够大时 f(n) 是非负值（渐近正函数则是当 n 足够大时总为正值）。这就要求函数 g(n) 本身也必须是渐近非负的，否则集合 就是空集。因此，假定 记号中用到的每个函数都是渐近非负的。

例子：

例 1：证明 。

首先要确定常数 ， 和 ，使得对所有的 n≥，即

成立，用 除不等式得

右边的不等式在 时对所有的 成立。同样，左边的不等式可以让 时对所有的 成立。这样，通过选择 ，，以及 ，可以证明 。当然，还存在其他的常数选择，而重要的是确实存在某个选择。需要注意的是，这些常数依赖于函数 ，中不同的函数通常需要不同的常数。

例 2: 证明 ≠。

使用反证法进行证明，假设存在常数 和 ，使对所有的 ，有 ；这样就有 ，这对于任意大的 n 是不可能成立的，因为 是常数。

例 3: 任意的二次函数 ，其中 a，b 和 c 都是常数，且 。

舍掉低阶项并忽略常数项得出 。可以发现，当常数 ， 且 ，时，对于所有的 ，满足 。

O 记号

定义：

记号渐近地给出了一个函数的上界和下界。当只有一个渐近上界时，使用 O 记号。对于给定函数 g(n)，用 O(g(n))（读作“大 Og(n)”，有时仅读作”Og(n)”）来表示以下函数的集合：O(g(n))={f(n): 存在正常量 c 和 ，使得对所有 n≥，有 0≤f(n)≤cg(n)}

解释

上图说明了 O 记号的直观意义，对位于 右边的 n 值，函数 f(n) 的值在 g(n) 之下。
利用 O 记号，我们常常能通过查看算法的总体结构来描述算法的运行时间。例如，插入排序算法中的二重循环结构立即能引出其最坏情况运行的上界 ，内循环每一轮迭代的代价以 （常量 ）为上界，下标 i 和 j 最大可以取到 n，对于 个 i 值和 j 值对中的每一对，内循环至多执行一次。

记号

定义

正如 O 记号提供了一个函数的渐近上界， 记号提供了渐近下界。对于给定的函数 g(n)，用 (读作“大 ”，有时仅读作“”)来表示以下函数的集合： = {f(n)：存在正常量 c 和 ，使得对所有 n≥，有 0≤cg(n)≤f(n)}

解释

o 记号

O 记号与 o 记号的定义是类似的，主要区别在于对 f(n)=O(g(n))，界 0≤ f(n)≤ cg(n) 对某个常数 c>0 成立，但对 f(n)=o(g(n))，界 0≤ f(n)≤ cg(n) 对所有常数 c>0 成立。从直觉上看，在 o 表示中当 n 趋于无穷时，函数 f(n) 相对于 g(n) 来说就不重要了，即

记号

定义

表示非渐近紧确的下界，它的一种定义为 ，当且仅当 。 的形式定义为集合 ，对任意正常数 c>0，存在常数 ，有 。
例如：，但 ≠。关系 f(n)= 意味着

如何这个极限存在。也就是说当 n 趋于无穷时，f(n) 相对 g(n) 来说变得任意大了。

一个例子

设 为一个 n 的 d 次多项式，其中 ，令 k 为一个常数。利用渐近记号的定义来证明如下性质：
1. 若 k≥d，则 。
2. 若 k≤d，则 。
3. 若 k=d，则 。
4. 若 k>d，则 。
5. 若 k<d，则 。

解：该公式可以改写为：

对于性质 1

使

得到

进一步化简得到

使 ，则

此时对于 n>时，，性质 1 得到证明。
同理，当 时，可以证明性质 2 。
其余性质的证明方式类似。