Algorithms usually possess the following qualities and capabilities:

• Easily modifiable if necessary.
• They are easy, general and powerful.
• They are correct for clearly defined solution.
• Require less computer time, storage and peripherals i.e. they are more economical.
• They are documented well enough to be used by others who do not have a detailed knowledge of the inner working.
• They are not dependable on being run on a particular computer.
• The solution is pleasing and satisfying to its designer and user.
• They are able to be used as a sub-procedure for other problems. 

Two or more algorithms can solve the same problem in different ways. So, quantitative measures are valuable in that they provide a way of comparing the performance of two or more algorithms that are intended to solve the same problem. This is an important step because the use of an algorithm that is more efficient in terms of time, resources required, can save time and money.

Computational Complexity 

We can characterize an algorithm’s performance in terms of the size (usually n) of the problem being solved. More computing resources are needed to solve larger problems in the same class. The table below illustrates the comparative cost of solving the problem for a range of n values.

Log2n	n	n log2n	n2	n3	2n
1	2	2	4	8	4
3.322	10	33.22	102	103	>103
6.644	102	664.4	104	106	>> 1025
9.966	103	9966.0	106	109	>> 10250
13.287	104	132877	108	1012	>> 102500

The above table shows that only very small problems can be solved with an algorithm that exhibit exponential behaviour. An exponential problem with n=100 would take immeasurably longer time. At the other extreme, for an algorithm with logarithmic dependency would merely take much less time (13 steps in case of log2n in the above table). These examples emphasize the importance of the way in which algorithms behave as a function of the problem size. Analysis of an algorithm also provides the theoretical model of the inherent computational complexity of a particular problem.

To decide how to characterize the behaviour of an algorithm as a function of size of the problem n, we must study the mechanism very carefully to decide just what constitutes the dominant mechanism. It may be the number of times a particular expression is evaluated, or the number of comparisons or exchanges that must be made as n grows. For example, comparisons, exchanges, and moves count most in sorting algorithm. The number of comparisons usually dominates so we use comparisons in computational model for sorting algorithms.

The Order of Notation

The O-notation gives an upper bound to a function within a constant factor. For a given function g(n), we denote by O(g(n)) the set of functions.

O(g(n)) = { f(n) : there exist positive constants c and n0, such that 0 <= f(n) <= cg(n) for all n >= n0 }

Using O-notation, we can often describe the running time of an algorithm merely by inspecting the algorithm’s overall structure. For example a double nested loop structure of the following algorithm immediately yields O(n2) upper bound on the worst case running time.

for i=0 to n
 for j=0 to n
 print i,j
 next j
next i

What we mean by saying “the running time is O(n2 )” is that the worst case running time ( which is a function of n) is O(n2 ). Or equivalently, no matter what particular input of size n is chosen for each value of n, the running time on that set of inputs is O(n2 ). 

Rules for using the Big-O Notation

Big-O bounds, because they ignore constants, usually allow for very simple expression for the running time bounds. Below are some properties of big-O that allow bounds to be simplified. The most important property is that big-O gives an upper bound only. If an algorithm is O(N2), it doesn’t have to take N2  steps (or a constant multiple of N2). But it can’t take more than N2. So any algorithm that is O(N), is also an O(N2) algorithm. If this seems confusing, think of big-O as being like “<”. Any number that is < N is also <N2

1. Ignoring constant factors: O(c f(N)) = O(f(N)), where c is a constant; e.g. O(20 N3 ) = O(N3 )
2. Ignoring smaller terms: If a<b then O(a+b) = O(b), for example, O(N2 + N) = O(N2)
3. Upper bound only: If a<b then an O(a) algorithm is also an O(b) algorithm. For example, an O(N) algorithm is also an O(N2) algorithm (but not vice versa). 
4. N and log N are bigger than any constant, from an asymptotic view (that means for large enough N). So if k is a constant, an O(N + k) algorithm is also O(N), by ignoring smaller terms. Similarly, an O(log N + k) algorithm is also O(log N)
5. Another consequence of the last item is that an O(N log N + N) algorithm, which is O(N(log N + 1)), can be simplified to O(N log N)

Worst and Average Case Behavior

Worst and average case behaviors of the algorithm are the two measures of performance that are usually considered. These two measures can be applied to both space and time complexity of an algorithm. The worst case complexity for a given problem of size n corresponds to the maximum complexity encountered among all problems of size n. For determination of the worst case complexity of an algorithm, we choose a set of input conditions that force the algorithm to make the least possible progress at each step towards its final goal.

In many practical applications it is very important to have a measure of the expected complexity of an algorithm rather than the worst case behavior. The expected complexity gives a measure of the behavior of the algorithm averaged over all possible problems of size n.

As a simple example: Suppose we wish to characterize the behavior of an algorithm that linearly searches an ordered list of elements for some value x. 1 2 3 4 5 … … …. N

In the worst case, the algorithm examines all n values in the list before terminating.

In the average case, the probability that x will be found at position 1 is 1/n, at position 2 is 2/n and so on. Therefore,

Average search cost = 1/n(1+2+3+ …..+n)

                                                        = 1/n(n/2(n+1)) = (n+1)/2

Let us see how to represent the algorithm in a graphical form using a flowchart in the following section.