1. Theorems

• 모든 계수를 무시
  • $O(2N) → O(N)$
  • $O(3N^2) → O(N^2)$
  • $O(10) → O(1)$
• 아주 작은 terms 무시
  • $O(N+1) → O(N)$
  • $O(N^2+3N+5) → O(N^2)$
  • $O(2^N+4N^3+5N^2+7N+6) → O(2^N)$

2. Big-O examples and comparison

• $O(1)$ : bounded(by a constant) time
• $O(log{N}) = O(log{2}{N})$: logarithmic time
• $O(N)$ : linear time
• $O(NlogN) = O(Nlog_2{N})$: $O(Nlog_2{N})$ time
• $O(N^2)$: quadratic time
• $O(2^N)$: exponential time

3. Exercises

• $O(5N + 3M^2)$

  → $O(N+M^2)$

• Copy the Array A into empty Array B(A’s length = N)

  → $O(N)$

• Find the max/min item in Array C(C’s length = N)

  → $O(N)$

• Sort the array D(D’s length = N)

  • ex) [7,2,5,6,3] → [2,3,5,6,7]

  → $O(N^2)$

• Find the N-th item in the Fiboonacci series

  • Fibo(N) = Fibo(N-1) + Fibo(N-2)

  → $O(2^N)$