• Time complexity에 관한 이야기.
• 알고리즘이 문제를 푸는 데 걸리는 시간; running time
• 정확한 러닝 타임을 알 수 없다.

Asymptotic efficiency

• n이 무한대로 갔을 때를 수학적으로 표시함.
• 차수가 낮은 항이나 상수는 잘 고려하지 않는다.

• BigOh는 worst case(upper bound), Omega는 best case(lower bound)이다.

O-notation - upper bound

• O(g(n)) = { f(n) : 양의 상수 c와 n0이 존재할 때 → 0 ≤ f(n) ≤ c g(n) for all n ≥ n0 }
  • n→ 무한대, f(n)/g(n)이, (로피탈 정리 이용해서) c가 무한대보다 작을 때, f(n) = O(g(n))이라고 표현할 수 있다
  • n0부터 c*g(n) ≥ f(n)

ex. 2n^2+1 = O(n^2), with c = ? and n0 = ?

• c=3, n=1일 때 만족한다.
• c=3, n=2일 때 만족한다.

ex2. 2n^2=O(n^3), with c = ? , and n0 = ?

• c = 1, n0 = 2
  • n^3 = 8 <⇒ 2n^2 = 8
• c = 1, n0 = 3
  • n^3 = 27, 2n^2 = 18

Omega-notation - lower bound

• Omega(g(n)) = { f(n) : 양의 상수 c와 n0가 존재할 때, 0 ≤ c g(n) ≤ f(n), 모든 n ≥ n0에 대하여 }