Rules for ÒOÓ
Additive Rule
Additive Rule
lf+g ë O(max(f, g))
Here f+g means n Þ f(n) + g(n)
max(f, g) means n Þ max(f(n), g(n))
lCorollary: If g ë O(f), then f+g ë O(f)
lExample: For polynomials, the highest order term dominates, e.g.
n5+1000000n3+10000n2 ë O(n5)
Here f+g means n Þ f(n) + g(n)
max(f, g) means n Þ max(f(n), g(n))
lCorollary: If g ë O(f), then f+g ë O(f)
lExample: For polynomials, the highest order term dominates, e.g.
n5+1000000n3+10000n2 ë O(n5)