Big Oh notation

Let f(n) and g(n) be non-negative, non-decreasing functions of n. We say f(n) = O(g(n)) iff

? +ve constants c and no such that

f(n) ? c . g(n) for all n ? no

• I.e. f(n) grows no faster than g(n) (ignoring constant factors)

• Since we’re ignoring constant factors, typically choose g(n) to be “simple” looking:

Previous slide

Next slide

Back to first slide

View graphic version