때로는 알고리즘이 상한선 없이 최소한 어느 정도 걸린다고 해야 할 때도 있을 것입니다. 그럴 때는 big-Ω 표기법을 사용합니다. 여기서 Ω는 그리스 문자 "오메가"입니다.
실행 시간이 Ω(f(n)) \Omega(f(n)) 라면 n이 충분히 클 때 실행 시간은 어떤 상수 k에 대해 최소 k, dot, f, left parenthesis, n, right parenthesis입니다. 실행 시간이 Ω(f(n)) \Omega(f(n)) 인 경우는 다음과 같이 생각할 수 있습니다.
6n^2 vs 100n+300
여기서 실행 시간은 "f, left parenthesis, n, right parenthesis의 big-Ω"라고 합니다. 점근적 하한선을 표현하기 위해선 big-Ω 표기법을 사용하는데, 그 이유는 점근적 하한선은 충분히 큰 입력 크기에서 실행 시간을 밑에서 제한하기 때문입니다.
Θ(f(n)) \Theta(f(n)) 가 자동적으로 O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis를 의미하는 것과 마찬가지로 자동적으로 Ω(f(n)) \Omega(f(n)) 을 의미합니다. 그러므로 최악의 경우 이진 검색의 실행 시간은 Ω(lgn) \Omega(\lg n) 라고 할 수 있습니다. 또한 big-&Omega 표기법을 이용하여 정밀하진 않지만 올바른 표현을 할 수 있습니다. 예를 들어 주머니에 백만 달러가 있을 때, 주머니에 돈이 있긴 한데 최소한 10 달러는 된다고 말하는 것이 진실인 것처럼 이진 검색은 최소한 상수의 시간이 걸리므로 이진 검색의 최악의 경우의 실행 시간은 Ω(1) \Omega(1) 라고 말할 수 있습니다.

위 자료는 다트머스 대학교 컴퓨터공학과토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.