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

• how fast the computer is that you use for testing,
• whether you used an optimizing compiler,
• and the details of how the algorithm has been coded.
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,

• 3n is O(n)
• n2 is O(n3)
• 5n3 + 2n + 1 is O(n3)

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
1234
----
22712    n   rows
17034     n+1 columns
11356      n(n+1) is O(n2)
5678
-------
7006652

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.

isprime(N)
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.