실행 시간이 커지는 것을 일정 하한선과 상한선 내에서 점근적으로 제한하기 위해 big-Θ를 사용합니다. 때로는 상한선만을 정하고 싶을 수도 있습니다. 예를 들어 이진 검색의 최악의 경우의 실행 시간이 Θ(lgn) \Theta(\lg n) 라고 해도 이진 검색이 모든 경우에서 Θ(lgn) \Theta(\lg n) 시간 내에 실행된다고 말하는 것은 올바르지 않을 수 있습니다. 첫 번째 추측에서 목표 값을 알아낸 경우는 어떻게 될까요? 이 때는 Θ(1) \Theta(1) 시간에 실행됩니다. 이진 검색의 실행 시간은 결코 Θ(lgn) \Theta(\lg n) 보다 나쁘지 않고, 때로는 더 나은 결과를 나타내기도 합니다. "실행 시간은 최대한 이만큼 커지지만 더 천천히 커질 수도 있다"는 의미인 점근적 표기법 형태를 사용하는 것이 편리할 수도 있습니다. 이런 경우를 위해 "big-O" 표기법을 사용합니다.
실행 시간이 O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis이라면 충분히 큰 값인 n에 대해 실행 시간은 어떤 상수값 k에서 최대 k, dot, f, left parenthesis, n, right parenthesis가 됩니다. 실행 시간이 O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis인 경우에 대해 이렇게 생각할 수 있습니다:
6n^2 vs 100n+300
여기서는 실행 시간이 "f, left parenthesis, n, right parenthesis의 big-O"거나, 그냥 "f, left parenthesis, n, right parenthesis의 O"라고 표현합니다. 점근적 상한선에 대해서는 big-O 표기법을 사용하는데 이는 충분히 큰 입력 크기에 대하여 실행 시간의 상한선을 제시합니다.
이제 모든 경우에 대해 이진 검색의 실행 시간을 특정할 수 있는 방법이 생겼습니다. 이진 검색의 실행 시간은 항상 O(lgn) O(\lg n) 라고 할 수 있습니다. 최악의 경우의 실행 시간에 대해서 더욱 강력한 식을 만들 수도 있습니다. 바로 Θ(lgn) \Theta(\lg n) 이죠. 그렇지만 모든 경우를 포괄하는 일반적 표현으로는 이진 검색이 O(lgn) O(\lg n) 시간 내에 실행된다고 하는 것이 가장 강력하게 표현하는 것입니다.
If you go back to the definition of big-Θ notation, you'll notice that it looks a lot like big-O notation, except that big-Θ notation bounds the running time from both above and below, rather than just from above. If we say that a running time is Θ(f(n)) \Theta(f(n)) in a particular situation, then it's also O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis. For example, we can say that because the worst-case running time of binary search is Θ(lgn) \Theta(\lg n) , it's also O(lgn) O(\lg n) . The converse is not necessarily true: as we've seen, we can say that binary search always runs in O(lgn) O(\lg n) time but not that it always runs in Θ(lgn) \Theta(\lg n) time.
Because big-O notation gives only an asymptotic upper bound, and not an asymptotically tight bound, we can make statements that at first glance seem incorrect, but are technically correct. For example, it is absolutely correct to say that binary search runs in O, left parenthesis, n, right parenthesis time. That's because the running time grows no faster than a constant times n. In fact, it grows slower. Think of it this way. Suppose you have 10 dollars in your pocket. You go up to your friend and say, "I have an amount of money in my pocket, and I guarantee that it's no more than one million dollars." Your statement is absolutely true, though not terribly precise. One million dollars is an upper bound on 10 dollars, just as O, left parenthesis, n, right parenthesis is an upper bound on the running time of binary search. Other, imprecise, upper bounds on binary search would be O, left parenthesis, n, start superscript, 2, end superscript, right parenthesis, O, left parenthesis, n, start superscript, 3, end superscript, right parenthesis, and O, left parenthesis, 2, start superscript, n, end superscript, right parenthesis. But none of Θ(n) \Theta(n) , Θ(n2) \Theta(n^2) , Θ(n3) \Theta(n^3) , and Θ(2n) \Theta(2^n) would be correct to describe the running time of binary search in any case.

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