A measure of Efficiency

How can we measure how efficient an algorithm is? Measuring the time taken to execute on a machine is definitely not appropriate, since the time would depend on the hardware of the machine. Instead, we define some operations of the algorithm to be fundamental, then analyse the number of operations it would require. This is the big-O notation.

Big-O Notation

Algorithms also depend on the amount of data in the set of inputs given. We refer to the input size as n. Then an algorithm like linear search would have the time complexity O(n); algorithms like bubble sort would be O(n^2). Typical complexity measures are:

  • O(1) (constant time)
  • O(lg n)
  • O(n)
  • O(lg n)
  • O(n^2)
  • O(2^n)
  • O(n!)

Asymptotic Analysis

The mathematical basis of measuring time complexity comes from a method of comparing functions, called Asymptotic Analysis. Formally, the functions f(x) and g(x) are asymptotically equivalent if the limit of f(x)/g(x) as x approaches infinity is equal to 1. The functions f(x) = x and g(x) = x + 1 are asymptotically equivalent.