9.1. Big-O Notation

Big-O notation

Imagine doing experiments to measure the amount of time that a particular algorithm uses on a collection of test inputs. You expect the amount of time to be a function of the size of the input.

But your exact results will depend not just on the algorithm or the input, but on factors such as

When giving time functions for algorithms, we usually suppress constant factors so that those influences are irrelevant.

Suppose that f(n) and g(n) are two functions that each take an integer parameter and yield an integer result.

Definition. f(n) is O(g(n)) if
there exists a constant c > 0 such that
  for all sufficiently large n
    f(n) ≤ cg(n).

For example,

Running time of algorithms

Normally, we judge the amount of time that an algorithm uses as a function of the number of characters that are needed to write down the input. By convention, the input length is n.

For example, there is an algorithm that tells whether a number is a palindrome (the same forwards and backwards) that takes time O(n).

The multiplication algorithm that you learned in elementary school probably takes time O(n2) to multiply two n-digit numbers.

        5678    n digits each
       22712    n   rows
      17034     n+1 columns
     11356      n(n+1) is O(n2)

You will need to be careful to remember that n is the number of characters in the input. Consider the following algorithm to check whether a number N is prime.

  for k = 2, ..., N-1
    if k is a factor of N
      return false
    end if
  end for
  return true

When N is prime, the loop goes around N − 2 times. Is that O(n) time? No! N is not the length of the input!

With n decimal digits you can write down a number that is just a bit smaller than 10n. So it is reasonable to assume that N ≈ 10n.

But that means the algorithm above does about 10n divisions (to see if k is a factor of N). If each division takes time proportional to n2, the total time, in the worst case, is O(n210n).

Just for perspective, there are very roughly 1050 protons in the earth, and astronomers estimate that there are roughly 1080 protons in the visible universe.

Is there a faster algorithm to determine whether a given integer is prime? Yes. We will come back to that later.