朗道符号
大O符号是由德国数论学家保罗·巴赫曼（Paul Bachmann）在其1892年的着作《解析数论》（Analytische Zahlentheorie）首先引入的。而这个记号则是在另一位德国数论学家艾德蒙·朗道（Edmund Landau）的着作中才推广的，因此它有时又称为朗道符号（Landau symbol）。代表“order of ...”（……阶）的大O，最初是一个大写的希腊字母'Ο'（Omicron），现今用的是英文大写字母'O'，但从来不是阿拉伯数字'0'。这个符号有两种形式上很接近但迥然不同的使用方法：无穷大渐近与无穷小渐近。然而这个区别只是在运用中的而不是原则上的——除了对函式自变数的一些不同的限定，“大O”的形式定义在两种情况下都是相同的。
无穷大渐近
大O符号在分析算法效率的时候非常有用。举个例子，解决一个规模为 n 的问题所花费的时间（或者所需步骤的数目）可以被求得：T(n) = 4n^2 - 2n + 2。
当 n 增大时，n^2; 项将开始占主导地位，而其他各项可以被忽略——举例说明：当 n = 500，4n^2; 项是 2n 项的1000倍大，因此在大多数场合下，省略后者对表达式的值的影响将是可以忽略不计的。
进一步看，如果我们与任一其他级的表达式比较，n^2; 项的係数也是无关紧要的。例如一个包含 n^3; 或 n^2项的表达式，即使 T(n) = 1,000,000n^2;，假定 U(n) = n^3;，一旦 n 增长到大于1,000,000，后者就会一直超越前者(T(1,000,000) = 1,000,000^3; = U(1,000,000))。
这样，大O符号就记下剩余的部分，写作：
T(n）∈O(n^2)
并且我们就说该算法具有 2阶的时间複杂度。
无穷小渐近
大O也可以用来描述数学函式估计中的误差项。例如：
e^x=1+x+x^2/2+O(x^3) 当 x→0 时
这表示，如果 x 足够接近于0，那么误差（e^x− (1 + x + x^2 / 2)的差）的绝对值小于 x^3的某一常数倍。
常用的函式阶
下面是在分析算法的时候常见的函式分类列表。所有这些函式都处于 n 趋近于无穷大的情况下，增长得慢的函式列在上面。 c 是一个任意常数。
| 符号 | 名称 |
|---|---|
| O(1) | 常数（阶，下同） |
O(log*n) | 叠代对数 |
O(log n) | 对数 |
O[(log n)^c] | 多对数 |
O(n) | 线性，次线性 |
O(n log n) | 线性对数，或对数线性、拟线性、超线性 |
O(n^2) | 平方 |
O(n^c),Integer(c>1) | 多项式，有时叫作“代数”（阶） |
O(c^n) | 指数，有时叫作“几何”（阶） |
O(n!) | 阶乘，有时叫做“组合”（阶） |
