소(little-o) 표기법이란?
알고리즘의 점근적 분석(asymptotic analysis)에서는 빅오(Big-O), 빅오메가(Big-Omega), 빅세타(Big-Theta) 표기법 외에도 몇 가지 보조 표기법이 사용됩니다. 그중 하나가 바로 소(little-o) 표기법입니다.
소 표기법은 타이트(tight)해질 수 없는 상한, 즉 엄격한 의미의 느슨한 상한(loose upper bound)을 나타낼 때 사용됩니다. 빅오 표기법이 '이하(≤)'의 개념이라면, 소 표기법은 '미만(<)'에 해당하는 더 강한 조건이라고 이해하면 쉽습니다.
수학적 정의
양의 실수를 입력으로 받는 두 함수 f(n)과 g(n)가 있다고 가정해 봅시다. 다음 조건을 만족할 때 함수 f(n)은 o(g(n))이라고 말할 수 있습니다.
임의의 양의 실수 상수 c > 0에 대해, 어떤 정수 상수 n₀ ≥ 1이 항상 존재하여 모든 n ≥ n₀에 대해 다음 부등식이 성립하는 경우입니다.
0 ≤ f(n) < c × g(n)
소 표기법의 수학적 관계
극한(limit)을 활용하면 f(n) = o(g(n))을 다음과 같이 간결하게 표현할 수 있습니다.
lim(n→∞) f(n) / g(n) = 0
즉, n이 무한대로 커질 때 f(n)과 g(n)의 비율이 0으로 수렴한다는 의미입니다. 이는 f(n)이 g(n)에 비해 상대적으로 훨씬 느리게 증가한다는 것을 수학적으로 보장합니다.
예제: 소 표기법 확인하기
f(n) = n2, g(n) = n3일 때, f(n) = o(g(n))이 성립하는지 확인해 보겠습니다.
lim(n→∞) f(n) / g(n) = lim(n→∞) n2 / n3 = lim(n→∞) 1 / n = 0
계산 결과가 0이므로 앞서 언급한 극한 조건을 만족합니다. 따라서 f(n) = o(g(n))이 성립함을 알 수 있습니다.
빅오(Big-O)와 소(little-o)의 차이
두 표기법의 차이를 명확히 구분하면 점근적 분석이 훨씬 쉬워집니다.
- 빅오(Big-O): f(n) ≤ c × g(n) — 상한이 타이트할 수도 있는 조건 (≤)
- 소(little-o): f(n) < c × g(n) — 상한이 결코 타이트해질 수 없는 조건 (<)
예를 들어 f(n) = n인 경우, f(n) = O(n2)이면서 동시에 f(n) = o(n2)도 성립합니다. 하지만 f(n) = O(n)은 참이더라도 f(n) ≠ o(n)입니다. 이처럼 소 표기법은 빅오보다 더 엄격한 상한 관계를 요구한다는 점이 핵심입니다.