1.1.2 오메가 표기법
정의 모든 n ≥ n0에 대해 조건 cg(n) ≤ f(n)을 만족하는 두 양의 상수 c와 n0이 있다면 f(n)은 g(n)의 오메가(omega) 또는 f(n) = Ω(g(n))입니다.
cg(n)은 f(n)의 하한(lower bound)3이며, 함수 f(n)의 증가 속도는 cg(n)보다 빠릅니다.
▲ 그림 1-2 오메가 표기법
f(n) = Ω(g(n))으로 표기하는 f(n) = nc와 g(n) = cn의 관계를 그림에서 살펴보세요.
3 역주 하한은 알고리즘의 실행 시간이 최선일 때도 이 시간과 같거나 느리다는 뜻입니다.