Complexity of an algorithm is the measure of analysis of algorithm. Analyzing an algorithm means predicting the resources that the algorithm requires such as memory, communication bandwidth, logic gates and time. Most often it is computational time that is measured for finding a more suitable algorithm. This is known as time complexity of the algorithm. The running time of a program is described as a function of the size of its input. On a particular input, it is traditionally measured as the number of primitive operations or steps ****. Worst case analysis of an algorithm is an upper bound on the running time for any input. Knowing that in advance gives us a guarantee that the algorithm will never take any longer. Average case analysis of an algorithm means expected running time of an algorithm on average input data set. The average case is often as bad as the worst case. One problem with performing an average case analysis is that it is difficult to decide what constitutes an “average” input for a particular problem. Often we assume that all inputs of a given size are equally likely.
