What is order notation (or Big "O" notation)?
Order notation, or Big "O" notation, is a measure
of the running time of an algorithm, as it relates to the size of the input
to that algorithm. It is intended, not to measure the performance
of the machine on which the algorithm is run, but rather to strictly measure
the performance of the algorithm itself. Thus, since different
machines can vary in their speeds by some constant factor, we remove all
constant factors from consideration when we talk about order notation.
For example O(2) and O(1) are considered to be the same. Similarly,
O(n) is the same as O(2n), and the same as O(100n)
Some polynomial running times
O(1)
An algorithm with this running time is said to have
"constant" running time. Basically, this means the algorithm always
take about the same amount of time, regardless of the size of the input.
To state it technically, if an algorithm will never perform more than a
certain number of steps, no matter how large the input gets, then that
algorithm is considered to have a constant running time. For example,
an algorithm which consists of performing exactly 7 multiplication's has
a constant running time. An algorithm which always finishes in under
a year has a constant running time. Although constant time is the
best running time an algorithm can have, that algorithm could still be
considered bad if the total amount of time to run the algorithm were too
large, perhaps because there were many complex or unnecessary steps in
the algorithm.
Some examples of O(1) algorithms include: inserting
an element onto the front of a linked list, popping from or pushing onto
a stack, and retrieving the nth element of an array.
O(n)
An algorithm which runs in O(n) is said to have
a "linear" running time. This basically means that the amount of
time to run the algorithm is proportional to the size of the input.
To be technical, an algorithm which never performs more than certain number
of steps for each element in the input has a linear running time.
For example, an algorithm which sums the total of a list of numbers has
a linear running time, because the number of additions required is the
same as the number of elements (thus there is 1 addition for every element).
Some examples of O(n) algorithms include searching
through an unordered list, incrementing every element of an array, and
calculating fibonacci numbers using dynamic programming. There is
also a clever way to find the median element of a list in linear time.
O(n2)
An algorithm with this running time is said to have
"quadratic" running time. This means that whenever you increase the
size of the input by a factor of n, the running time increases by a factor
of n2. For example, if you double the size of the input
of a quadratic algorithm, then the running time will quadruple.
Some sorting algorithms, such as insertion sort and bubble sort,
have quadratic running times.
O(lgn)
An algorithm with O(lgn) running time is said to
have "logarithmic" running time. This means that as the size of the
input increases by a factor of n, the running time increases by a factor
of the logarithm of n. For example, if you increase the input size
of a O(lgn) algorithm by a factor of 1024, the running time will increase
by a factor of 10. This running time is better than O(n), but not
as good as O(1). As the input size gets large, however, the behavior
becomes comparable to O(1) in many circumstances.
Algorithms which search through ordered lists or
binary trees, as well as operations on heaps generally have logarithmic
running times.
O(nlgn)
An algorithm which has this order, will in increase
in running time proportionate to the size of the input times the logarithm
of the size of the input. Technically speaking, an algorithm which
when given an input of size n never performs more than cnlgn steps (for
some c which is always the same regardless of the value of n) has a running
time of O(nlgn). This running time is better than O(n2)
but not quite as good as O(n).
The fastest sorting algorithms, including mergesort
and quicksort, have O(nlgn) running times
Worse than polynomial running times
O(2n)
An algorithm with this running time is said to be
"exponential". This means that its running time will double every
time you add another element to the input. An algorithm with this
running time is generally considered to be too slow to be useful for anything
but the smallest of problems. For example, an O(2n) algorithm
which takes an input with 30 elements may need to perform as many as 1
billion steps. If the input has 40 elements then the 1 trillion steps
may be necessary. No computer in the world can do this in a reasonable
amount of time.
O(n!)
An algorithm with this running time is said to be
"factorial". This is worse than exponential. This means that
if the algorithms take an input of size n, the total time will be
proportional to n*(n-1)*(n-2)*...*2*1. For example, if an algorithm
with this running time were to take 8 elements in its input, the
number of steps would be proportional to 8*7*6*5*4*3*2*1 = 40320. When
the input size reaches 15, the number of steps may exceed 1 trillion.
An example of a factorial algorithm is one that calculates fibonacci
numbers recursively.
O(nn)
This running time is even worse than factorial.
An algorithm with this running time which takes 10 elements of input may
need to perform 10 billion steps.
Almost constant running times
O(lg*n)
This running time is called "log-star" time.
The log-star function calculates how many times you would need to take
the log of n before you would go below 2. For example: lg*4 = 2,
lg*16=3, lg*65536=4. lg* 1000000000000000 < 5. This function grows
so slowly, that for all practical purposes it may be considered constant.
Technically it is not constant, but no computer in the world can store
enough data to cause the total running time to increase more than a factor
of 5 of the total running time which the algorithm takes when the input
has just 2 elements.
O(a(m,n))
This function, which is called the inverse of Ackerman's
function, performs similarly to the log-star function. If m=2 then
this is equivalent to the log-star function, and if m>2 then this grows
even more slowly.