Summary

This is notebook copy from below reference.

Definition

f(n) = O(g(n)) means there are positive constant c and n0 ,such that f(n) <= cg(n) for all n > n0

big-o

Description

  • 某演算法的時間函數的上限(Upper bound)
  • 只要n大到某一個程度(n0)，就保證時間函數f(n)的數值一定小於等與g(n)函數
  • 在最壞的情況下，該演算法的時間函數f(n)之成長率最多會達到g(n)，而不會超過

Excercise

ex1

  • f(n) = 3n+2, 則 f(n) = O(n)， tip c只要比該項的比該項的
    常數値常數値大1即可!!再由c去推n0
  • 3n+2 <= 4n => n > 2

ex2

  • f(n) = 5n2+3n+2, 則 f(n) = O(n2)
  • 5n2+3n+2 ≤ 6n2 => 3n+2 ≤ n2 > 取 n0 = 4

Order

big-o

reference