란다우 표기법 / 빅 오 표기법 (Landau Notation / Big-O Notation) 는 다음과 같이 사용합니다.
두 함수 $f$, $g$에 대해 어떤 두 양의 상수 $x_{0}$, $C$가 존재하여 $x_{0} < x$인 모든 실수 $x$에 대해
$$
| f(x) | \leq C | g(x) |
$$
이면, $f(x) = O(g(x))$라 한다.
$|x|$는 절댓값 함수 입니다.
일반적으로 코딩 용어로는 그냥 "빅 오" 정도로 이야기하는 그 시간복잡도 표기입니다.
예를 들어, 선택 정렬 의 시간복잡도는 $O(n^2)$, 밀러-라빈 소수 판별법 의 시간복잡도는 $O(\log^{4} n)$ 입니다. $\log x$는 자연로그함수 입니다. (사실 로그함수의 경우 밑이 어떻든 상관이 없습니다. 모든 로그함수들은 상수배 차이가 납니다.)