O(g(n)) = {f(n) | 충분히 큰 모든 n에 대하여 f(n)<=c*g(n)인 양의 상수 c가 존재}

 ex) {3n², n²+n+3, n+2, nlogn, 3} ⊂ O(n²)

 

 Ω(g(n)) = {f(n) | 충분히 큰 모든 n에 대하여 c*g(n)<=f(n)인 양의 상수 c가 존재}

 ex) {n³, n²+3, 3n+2} ⊂ Ω(n)

 

 Θ(g(n)) = O(g(n)) ∩ Ω(g(n))

 = {f(n) | 충분히 큰 모든 n에 대하여 c₁*g(n)<=f(n)<=c₂*g(n)인 양의 상수 c₁, c₂가 존재}

 ex) {n²+n+3, 2n²+3} ⊂ Θ(n²)

 

 

일반적으로 입력 크기가 커질수록 알고리즘의 수행시간이 증가하므로, 수행시간을 입력 크기 n에 대한 함수로 표현한다. 이러한 표현을 시간복잡도라고 한다.

시간복잡도는 주로 점근적 상한 표기법(빅-오 표기법)으로 표현된다.