在分析算法性能的时候，通常有空间复杂度和时间复杂度两个维度，前者考虑的是对于存储空间的占用，后者考虑的是算法完成所需要的时间，在分析时候有许多记号用于不同需求时的表示。
通常来说复杂度与输入的规模有关，下文中 n 均表示输入规模。
Θ 记号
Θ(g(n)) 用来表示一类函数 f(n) ，存在 c1、c2 和 n0，使得对于所有 n≥n0，都有 0≤c1g(n)≤f(n)≤c2g(n)。
换句话说就是当 n 足够大以后，如上图所示，f(n) 会被始终夹在两者之间，那么就认为 f(n)∈Θ(g(n))，但通常来说用等号替代属于符号，即 f(n)=Θ(g(n))。
最为常见的是关于 n 的时间复杂度是多项式，在使用 Θ时通常我们可以仅保留最高阶项，并舍弃常数。例如 4n3+20n2+100 可以记作 Θ(n3)。
之所以可以这么做是因为我们往往考虑的是当 n 极大时候的性能，当 n 足够大时，低阶项无论前面常数多大也是无足轻重的，而最高阶系数仅对于定义中 c1 和 c2 选取有关，而不影响到 g(n)。所以一般来说都有
∀ p(n)=d∑i=0aini, 都有 p(n)=Θ(nd)其中 ai 都是常量且 ad>0。对于 0 阶多项式，即常数，一般记作 Θ(1)。
值得一提的是，在分析时间复杂度时候，n 较小的情况一般不考虑，因为绝大多数情况下考虑的是输入规模很大时候的性能，本文中的记号也都是设计用来考虑规模很大时候的性能。但在有些场景中 n 有限，此时低阶项系数可能仍发挥着不可忽视的作用，此时仅使用 Θ 可能并不能得到最优的方法。
O 记号
O(g(n)) 表示一类函数 f(n)，存在 c 和 n0，使得对于所有 n≥n0，都有 0≤f(n)≤cg(n)。一般读作“大 O”或者“Big-Oh”。
相比于 Θ 渐进的给出了上界和下届，O 只考虑渐近上届。因此类似于 n=O(n2) 也是合法的，因为很显然当 n 很大时，一次函数必定始终小于一个二次函数。
尽管可能会有那么一些不准确，但是可以用它来仅仅通过检查代码结构来描述运行时间。比如一个双重嵌套的循环，两个循环都与 n 有关，循环内是常数时间即可完成的，那么就可以得出一个 O(n2) 的上界。当然具体运行的时间依赖于具体输入，但至少利用 O 可以得到无论任何输入的一个最坏上界。
Ω 记号
Ω(g(n)) 表示一类函数 f(n)，存在 c 和 n0，使得对于所有 n≥n0，都有 0≥cg(n)≥f(n)。
与 O 记号类似，Ω 提供了一个渐进下界。
o 和 ω 记号
O 记号中给出的上界可能是渐进紧确的，也可能不是。例如 2n2=O(n2) 就是渐进紧确的，而 2n=O(n2)就不是。o 记号就是用来表示一个非渐进紧确的上界。相对于O的定义，要求对于任意 c>0 都存在 n0>0 有 0≤f(n)<cg(n)。
所以 2n=o(n2)，而 2n2≠o(n2)。对于 f(n)=o(g(n))，当 n 趋于无穷时，f(n) 相对于 g(n)就会显得微不足道，即 lim。
\omega 与 \Omega 间区别与 O 和 o 间关系相同，用来表示非渐进紧确的下界。例如 2n^2 = \omega (n)，而 2n \ne \omega (n^2)。对于 f(n)=o(g(n))，当 n 趋于无穷时，则有 \lim_{n\to \infty} \frac{f(n)}{g(n)} = \infty。
关系
定理
- 对于任意两个函数 f(n) 和 g(n)，有 f(n)=\Theta (g(n))，当且仅当 f(n) = O(g(n)) 且 f(n) = \Omega (g(n))。
传递性
- 若 f(n) = \Theta (g(n)) 且 g(n) = \Theta (h(n))，则有 f(n) = \Theta (h(n))
- 若 f(n) = O (g(n)) 且 g(n) = O (h(n))，则有 f(n) = O (h(n))
- 若 f(n) = \Omega (g(n)) 且 g(n) = \Omega (h(n))，则有 f(n) = \Omega (h(n))
- 若 f(n) = o (g(n)) 且 g(n) = o (h(n))，则有 f(n) = o (h(n))
- 若 f(n) = \omega (g(n)) 且 g(n) = \omega (h(n))，则有 f(n) = \omega (h(n))
自反性
- f(n) = \Theta (f(n))
- f(n) = O (f(n))
- f(n) = \Omega (f(n))
对称性
- f(n) = \Theta (g(n)) 当且仅当 g(n) = \Theta (f(n))
转置对称性
- f(n) = O (g(n)) 当且仅当 g(n) = \Omega (f(n))
- f(n) = o (g(n)) 当且仅当 g(n) = \omega (f(n))
运算法则
- O(f) + O(g) = O(max(f,g)) = O(f+g)
- O(f)O(g) = O(fg)
- O(cf(n)) = O(f(n))
总结
五种符号分别用于几种不同的比较情况，O(f) 记号代表了上确界小于等于 f 的函数集合，\Omega (f) 代表了下确界大于等于 f 的函数集合，\Theta (n) 则代表了上下确界均为 f 的函数集合。而 o 和 \omega 则与大写的类似，但不再允许相等。因此可以有如下的类比。
| 记号 | 类似 |
|---|---|
| f(n) = \Theta (g(n)) | a = b |
| f(n) = O (g(n)) | a \le b |
| f(n) = \Omega (g(n)) | a \ge b |
| f(n) = o (g(n)) | a < b |
| f(n) = \omega (g(n)) | a > b |