1.1.3 세타 표기법

정의 모든 n ≥ n₀에 대해 조건 c₁g(n) ≤ f(n) ≤ c₂g(n)을 만족하는 세 양의 상수 c₁, c₂, n₀이 있다면 f(n)은 g(n)의 세타(theta) 또는 f(n) = Θ(g(n))입니다.

함수 g(n)은 f(n)에 대해 점근적 근접 한계값(asymptotically tight bound)⁴입니다. 이때 함수 f(n)은 g(n)과 같은 비율로 증가합니다.

▲ 그림 1-3 세타 표기법

f(n) = 2n² + n과 g(n) = n²의 관계를 각 표기법에서 살펴보세요.

f(n) = O(g(n))

f(n) = Θ(g(n))

f(n) = Ω(g(n))

예를 들어 각각 f(n) = 10000 × n × log(n) 시간과 f(n) = n² 시간이 걸리는 두 정렬 알고리즘이 있다고 가정해 봅시다. 점근적 분석을 사용하면 첫 번째 알고리즘이 더 우수한데(상수를 무시하므로), n이 10000보다 작은 데이터 집합에 대해서는 실제로 두 번째 알고리즘이 더 빠르게 실행됩니다. 이 점근적 분석의 단점을 고려하며 알고리즘 사례 분석을 살펴봅시다.