当输入规模足够大，使得运行时间只与增长量级有关时，需要研究算法的渐近效率。也就是，当输入规模无限增加时，在极限中，算法的运行时间如何随着输入规模的变大而增加。本文中所用插图来自《算法导论》。
不同的记号从不同的方面来刻画一个算法的运行效率。将插入排序的最坏运行时间刻画为下式：
f(n) = an2+bn+c，其中 a,b,c为常量，n为输入规模。下面针对插入排序最坏运行时间f(n) 来展开讨论
根据与 f(n) 的大小关系，可分为 “==”, “>=” “>” “<=” “<” 共5种记号，分别为 ：
- Θ（西塔） “==”
- O （大o） “>=”
- o（小欧）”>”
- Ω（大欧米伽）”<=”
- ω（小欧米伽）
Θ（西塔）渐近紧确界
c1，c2为某个正常量，当n大于某一值时满足 **0 <= c1g(n) <= f(n) <= c2g(n)**，
插入排序最坏运行时间刻画为下式：f(n) = an2+bn+c
最坏运行时间：T(n) == Θ(g(n)) == Θ(n2)。一个渐近正函数的低阶项在确定渐近确界时可以被忽略，因为对很大的 n，它们是无足轻重的，当 n 较大时，高阶项的一个很小的部分足以支配所有的低阶项。
如下图所示：
O （大o）上界
c 为某个正常量，当n大于某一值时满足 cg(n) <= f(n)
插入排序最坏运行时间刻画为下式：f(n) = an2+bn+c
最坏运行时间 T(n) == O(g(n)) == O(n2)
如下图所示：
o（小欧）非渐近紧确的上界
任意正常量 c ，当 n 大于某w一值时，满足 **f(n)>cg(n) **
例如某个算法运行时间刻画为下式： f(n) = 2n
算法运行时间：T(n) == o(g(n)) == o(n2)
O 和 o 的区别：
f(n) = O(g(n))， 0 =< f(n) <= cg(n) 对某个大于 0 的常量 c 决定。
f(n) = o(g(n))， 0 =< f(n) <= cg(n) 对于所有大于 0 的常量 c成立。
Ω（大欧米伽）下界
O 记号提供了一个函数的渐近上界，Ω记号提供了渐近下界。
c 为某个正常量，当 n 大于某个值时，满足 0< c(g(n)) < f(n)
算法运行时间：T(n) == o(g(n)) == o(n2)
ω（小欧米伽）非渐近紧确的下界
ω 记号 和 Ω 记号 的关系类似于 o 记号和 O 记号的关系。
对任意的正常量 c，当 n 大于某个值时，满足 0 < cg(n) < f(n)
算法运行时间：T(n) == o(g(n))
Θ 和 O 的关系
**当只有一个渐近上界时，使用 O 记号。注意：f(n)=Θ(g(n))蕴涵着f(n)=O(g(n))，因为 Θ 是一个比 O 记号更强的概念，按照集合论中的写法，就是 Θ(g(n)) ⊆O(g(n)) ，关于任意二次函数an2+bn+c，其中 a>0，用Θ(n2)表示，任意这样的二次函数也在O(n2)中。更加让人惊讶的是，当 a>0时，任意线性函数 an+b 也在 O(n2)中 **
既然 O 记号描述上界，那么当它用来限制算法的最坏运行情况运行时间时，关于算法的每个输入上的运行时间，我们也有一个界。因此，对插入排序的最坏情况运行时间的界O(n2)也适用于该算法的每个输入的运行时间。然而，对插入排序的最坏情况运行时间的界Θ(n2)并未暗示该算法对每个输入的运行时间也是Θ(n2)，例如 当输入已排好序时，插入排序的运行时间为 Θ(n)。
从技术上讲，称插入排序的运行时间为 O(n2)有点不合适，因为对给定的 n，实际的运行时间是变化的，依赖于规模为 n 的特定输入。当我们说“运行时间为 O(n2) 时” ，意指存在一个O(n2)的函数 f(n)，使得对 n 的任意值，不管选择什么特定规模为 n 的输入，其运行时间的上界都是 f(n)。这也就是说最坏情况运行时间为 O(n2)
