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.

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

__ Definition.__
f(

there exists a constant

for all sufficiently large

f(

For example,

- 3
*n*is O(*n*) *n*^{2}is O(*n*^{3})- 5
*n*^{3}+ 2*n*+ 1 is O(*n*^{3})

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(*n*^{2}) to multiply two
*n*-digit numbers.

5678 n digits each 1234 ---- 22712 n rows 17034 n+1 columns 11356 n(n+1) is O(n^{2}) 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 10^{n}. So it is reasonable to assume that
*N* ≈ 10^{n}.

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

Just for perspective, there are very roughly 10^{50} protons in the earth,
and astronomers estimate that there are roughly 10^{80} 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.