정의의 범위
음이 아닌 비용 함수 f에서 f(n)=O(g(n))은 양의 상수 c와 기준 n₀가 존재하여 n≥n₀이면 f(n)≤cg(n)이라는 뜻이다. 작은 입력의 모든 값에서 같은 부등식이 성립할 필요는 없다.
직접 보이는 예
n≥1이면 5n+8≤13n이므로 5n+8은 O(n)이다. 상수항 8을 실제 계산에서 없애 버린다는 뜻이 아니라 충분히 큰 입력에서 선형 함수의 상수배로 묶을 수 있다는 뜻이다.
상한은 여러 개 가능
선형 함수는 O(n)일 뿐 아니라 O(n²)이기도 하다. 빅오는 반드시 가장 꼭 맞는 증가율만을 뜻하지 않는다. 양쪽에서 같은 차수로 묶는 더 강한 표현에는 세타 표기법을 사용한다.
최악의 경우와 별개
빅오라는 기호 자체가 최악의 경우를 뜻하지는 않는다. 최악 비용 함수에도 평균 비용 함수에도 상한을 붙일 수 있다. 어떤 함수를 분석하는지와 그 함수를 어떤 증가율로 묶는지를 나누어 읽는다.
관련 문서
시간 복잡도 / 공간 복잡도 / 세타 표기법 / 함수 / 알고리즘 / 일차함수 / 다항함수 / 분할 상환 분석