점근 표기법(Ο, Ω, Θ)

한 프로그램의 시간과 공간 복잡도에 대한 의미 있느(그러나 정확하지는 않은) 명령문을 만들 수 있게 해주는 용어를 소개하겠다. 지금부터 제시되는 함수 f와 g는 음수 값을 가지지 않는 함수들이다.

Ο(빅 오)의 정의 모든 n, n ≥ ni에 대해 f(n) ≤ cg(n)인 조건을 만족하는 두 양의 상수 c와 ni가 존재하기만 하면 f(n) = Ο(g(n))이다. (단, f(n) = Ο(g(n))과 Ο(g(n)) = f(n)이 동일하지는 않다.

여기의 기호 '='은 '동등하다'가 아니라 '~이다'라고 해석해야 한다.) 예를 들어 Ο(n^2)이라고 한다면 이는 최고차항이 n^2보다 크지 않은 함수를 말한다. f(n) = Ο(g(n))이 의미상으로 유익하기 위해서는 g(n)은 f(n) = Ο(g(n))이 되도록 가능한 한 작아야 한다.

연산 시간이 상수인 것을 의미할 때 Ο(1)이라 쓴다. Ο(n)은 선형이라 하고, Ο(n^2)은 평방형, Ο(n^3)은 입방형, 그리고 Ο(2^n)은 지수형...