Big-O와 Little-O 표기법, 무엇이 다를까?
알고리즘의 시간 복잡도나 함수의 증가율을 분석할 때 자주 등장하는 점근 표기법(asymptotic notation) 중에는 Big-O(O)와 Little-o(o)가 있습니다. 두 표기법은 이름만 들으면 비슷해 보이지만, 수학적으로 엄밀하게 따져 보면 중요한 차이가 있습니다.
Big-O(O)의 정의
e ∈ O(g)는 본질적으로 다음을 의미합니다.
- 적어도 하나의(at least one) 상수 l > 0에 대하여, 부등식 e(x) < l·g(x)가 모든 x > a에 대해 성립하도록 만드는 상수 a가 존재한다.
즉, 적절한 배율 상수 l 하나만 곱하면 g(x)가 e(x)를 넘어설 수 있다면 충분합니다.
Little-O(o)의 정의
e ∈ o(g)는 본질적으로 다음을 의미합니다.
- 모든(every) 상수 l > 0에 대하여, 부등식 e(x) < l·g(x)가 모든 x > a에 대해 성립하도록 만드는 상수 a가 존재한다.
상수 l을 아무리 작게 잡아도 결국 g(x)가 e(x)를 앞지르므로, e는 g보다 확실히 느리게 증가해야 한다는 훨씬 강한 조건입니다.
핵심 차이: ≤ 와 < 의 관계
두 표기법의 차이를 직관적으로 요약하면 다음과 같습니다.
- e ∈ O(g): e의 점근적 증가율은 g보다 빠르지 않다(no faster than). 마치 부등호 ≤에 해당합니다.
- e ∈ o(g): e의 점근적 증가율은 g보다 엄격히 느리다(strictly slower). 마치 부등호 <에 해당합니다.
따라서 Big-O는 같은 증가율인 경우도 포함하지만, Little-o는 반드시 증가율 자체가 낮아야만 성립합니다.
예시로 확인하기
x2 ∈ O(x2) // 증가율이 같으므로 Big-O는 성립
x2 ∉ o(x2) // 증가율이 같으므로 Little-o는 성립하지 않음
x2 ∈ o(x3) // 증가율이 엄격히 느리므로 Little-o 성립
같은 방식으로 n·log n ∈ o(n²)가 성립하는 반면, n·log n ∈ O(n·log n) 역시 성립하지만 n·log n ∉ o(n·log n)입니다. 이처럼 Big-O는 상한선의 존재 여부를, Little-o는 그 상한선이 도달 불가능할 정도로 높다는 사실을 각각 표현한다고 이해하면 됩니다.