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
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,
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.