CSC300: Approximation [8/9]

Often details are not important

We write f(n) ~ g(n) if f and g are more or less the same

• See Section 1.4 of Algorithms for a formal definition
• Roughly, they fit the same curve

We say f(n) is O(g(n)) if f(n) ~ a * g(n), for some constant a

• Called order of growth
• Called time complexity
• Called Big Oh