선형 검색을 구현한 간단한 예를 살펴봅시다:
var doLinearSearch = function(array) {
  for (var guess = 0; guess < array.length; guess++) {
    if (array[guess] === targetValue) { 
        return guess;  // 찾은 경우
    }
  }
  return -1;  // 찾지 못한 경우
};
배열의 크기(array.length)를 n으로 나타내기로 합시다. for 문이 실행될 수 있는 최대 횟수는 n이고, 이 최악의 경우는 검색 값이 배열에 없을 경우에 일어납니다. for 문이 반복될 때마다 guessarray.length 비교하기, array[guess]targetValue 비교하기, 가능하다면 guess 값 리턴, 그리고 guess 값 하나 증가와 같은 여러가지 일을 수행해야 합니다. 이와 같은 작은 계산은 실행될 때마다 일정한 시간이 필요합니다. c, start subscript, 1, end subscript가 루프를 한 번 도는데 드는 시간이라면 for 루프가 n번 반복될 때 n번을 모두 반복하는데 드는 시간은 c, start subscript, 1, end subscript, dot, n가 됩니다. 여기서 c, start subscript, 1, end subscript의 값이 무엇인지는 알 수 없습니다. 왜냐하면 이 값은 컴퓨터의 속도, 사용되는 프로그래밍 언어, 소스 프로그램을 실행가능한 코드로 번역하는 컴파일러나 인터프리터, 그 외 다른 요소에 따라 달라지기 때문입니다. 이 코드에는 for 루프 초기화 작업(guess를 0으로 초기화하는 작업)과 마지막에 -1를 리턴하는 작업 등 여분의 오버헤드가 약간 더 있습니다. 이 추가된 시간을 c, start subscript, 2, end subscript라고 부르기로 합시다. 이 역시 상수값입니다. 그러므로 최악의 경우 선형 검색에 드는 총 시간은 c, start subscript, 1, end subscript, dot, n, plus, c, start subscript, 2, end subscript가 됩니다
이제까지 설명했듯이 상수 인자인 c, start subscript, 1, end subscriptc, start subscript, 2, end subscript을 안다고 해서 실행 시간이 커지는 비율을 알 수는 없습니다. 중요한 것은 선형 검색의 최악의 경우의 실행 시간은 배열 크기인 n에 따라 커진다는 것입니다. 여기서 실행시간을 표시하기 위해 사용하는 표기법은 Θ(n) \Theta(n) 입니다. 이는 그리스어인 "세타"로 "n의 빅 세타 " 또는 그냥 "n의 세타"라고 읽습니다.
특정 실행 시간이 Θ(n) \Theta(n) 이라고 하는 것은 n이 충분히 크다면 실행 시간이 어떤 상수 k, start subscript, 1, end subscriptk, start subscript, 2, end subscript에 대하여 최소 k, start subscript, 1, end subscript, dot, n이며 최대 k, start subscript, 2, end subscript, dot, n가 된다는 뜻입니다. 아래 그림을 보면 Θ(n) \Theta(n) 에 대해 이해할 수 있습니다.
6n^2 vs 100n+300
n의 작은 값에 대해서는 k, start subscript, 1, end subscript, dot, nk, start subscript, 2, end subscript, dot, n와 실행 시간을 어떻게 비교하는지는 고려하지 않습니다. 그렇지만 n값이 충분히 커지면 점선에서 오른쪽 실행 시간은 반드시 k, start subscript, 1, end subscript, dot, nk, start subscript, 2, end subscript, dot, n 사이에 있게 됩니다. k, start subscript, 1, end subscriptk, start subscript, 2, end subscript 라는 상수가 있다면 실행 시간은 Θ(n) \Theta(n) 라고 할 수 있습니다.
big-Θ 표기법이 단지 n값에만 제한되지는 않습니다. n, start superscript, 2, end superscript이나 nlgn n \lg n 같이 n에 관한 어떤 함수에서나 이를 이용할 수 있습니다. 아래 그림을 보면 어떤 함수 f, left parenthesis, n, right parenthesis에 대하여 실행 시간이 Θ(f(n)) \Theta(f(n)) 이라는 의미가 무엇인지 알 수 있습니다:
6n^2 vs 100n+300
n값이 충분히 커지면 실행 시간은 k, start subscript, 1, end subscript, dot, f, left parenthesis, n, right parenthesisk, start subscript, 2, end subscript, dot, f, left parenthesis, n, right parenthesis 사이에 있게 됩니다.
실제로 상수 인자와 낮은 차원의 항목은 그냥 생략합니다. big-Θ 표기법을 사용하는 또다른 이점은 우리가 사용하는 시간 단위를 고려할 필요가 없다는 것입니다. 예를 들어 실행시간이 6, n, start superscript, 2, end superscript, plus, 100, n, plus, 300 마이크로 초라고 계산한다고 가정해 봅시다. 아니면 밀리 초일 수도 있을겁니다. big-Θ 표기법에서는 이를 언급하지 않습니다. 또한 계수인 6과 저차원 항목인 100, n, plus, 300을 생략하고 그냥 실행 시간이 Θ(n2) \Theta(n^2) 라고 할 수 있습니다.
big-Θ표기법을 사용하는 것은 실행 시간에 대해 점근적으로 근접한 한계값이 있다고 표현하는 것입니다. "점근적으로"라는 말을 쓰는 이유는 큰 값의 n에 대해서만 적용되기 때문입니다. "근접한 한계값"이라는 말은 위, 아래로 상수값 내에서 실행 시간을 좁힐 수 있다는 뜻입니다.

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