점근 상한 표기(Big-O notation)f(n) ≤ c g(n)이 n ≥ n₀인 모든 입력에서 성립하는 상한이다.

Ωc g(n) ≤ f(n)이 n ≥ n₀인 모든 입력에서 성립하는 하한이다.

Θ같은 g(n)으로 양쪽 부등식이 모두 성립한다.

c와 n₀가 부등식의 성립 구간을 정한다

함수와 관계를 바꾸면 성립 조건, 현재 부등식, 반례가 처음 나타나는 지점이 함께 바뀐다.

함수 쌍f=4n+12, g=nf=n²+2n, g=n²f=n, g=n²

관계Big-OΩΘ

상한 상수 c₂

5.00

하한 상수 c₁

1.00

시작점 n₀

12

현재 상수와 시작점

해석 조건

반례가 처음 나타나는 지점

Θ는 두 방향의 부등식이 모두 성립해야 한다

위 절에서 고른 함수, 관계, c와 n₀를 그대로 쓴다. 한쪽 경계가 맞더라도 반대쪽 경계가 없으면 Θ가 아니다.

상한 방향

하한 방향