시간복잡도

• 빅오 (O notation)

f(n)= O(g(n)) : if and only if there exist positive constant c and n0 such that 0≤ |f(n)| ≤ c|g(n)| for all n ≥ n0.

즉 일정 c,n0부터는 g(n)이 항상 f(n)보다 큰 함수를 의미한다. 이를 상한이라고 이해하면되는데, 정의만 따지자면 사실 f(n) = n+1 에 대해서 빅오는 O(n), O(n²) 모두 가능하다. 하지만 실질적으로 tightest bound인 n를 사용한다.

• 빅 오메가 (Ω notation)

f(n)= Ω(g(n)) : if and only if there exist positive constant c and n0 such that 0≤ c|g(n)| ≤ |f(n)| for all n ≥ n0.

빅오와 반대로 하한을 의미하는 함수, 여기서도 마찬가지로 f(n)=n²+1에 대해서 빅오메가는 Ω(n²),Ω(n), Ω(1) 모두 가능하지만, 실질적으로 tightest bound인 Ω(n²)을 사용한다.

• 빅 세타 (Θ notation)

f(n)= Ω(g(n)) : if and only if there exist positive constant c1, c2 and n0 such that 0≤ c1|g(n)| ≤ |f(n)| ≤c2|g(n)| for all n ≥ n0.

상한과 하한을 모두 만족하기 때문에 tight bound라고 할 수 있음.

• Arithmetics of Big-O Notation

1. if f(n) is O(g(n)), c*f(n) is also O(g(n)), where c is a constant.
2. if both f1(n) and f2(n) are O(g(n)), f1(n) + f2(n) is O(g(n)).
3. if f1(n) is O(g1(n)) and f2(n) is O(g2(n)), f1(n)*f2(n) is O(g1(n)*g2(n)).