Analysis Of Insertion Sort
Analysis of insertion sort: The time taken by the INSERTIONSORT procedure depends on the input: sorting a thousand numbers takes longer than sorting three numbers. Moreover, INSERTIONSORT can take different amounts of time to sort two input sequences of the same size depending on how nearly sorted they already are. In general, the time taken by an algorithm grows with the size of the input, so it is traditional to describe the running time of a program as a function of the size of its input. To do so, we need to define the terms "running time" and "size of input" more carefully.
The best notion for input size depends on the problem being studied. For many problems, such as sorting or computing discrete Fourier transforms, the most natural measure is the number of items in the inputfor example, the array size n for sorting. For many other problems, such as multiplying two integers, the best measure of input size is the total number of bits needed to represent the input in ordinary binary notation. Sometimes, it is more appropriate to describe the size of the input with two numbers rather than one. For instance, if the input to an algorithm is a graph, the input size can be described by the numbers of vertices and edges in the graph. We shall indicate which input size measure is being used with each problem we study.
The running time of an algorithm on a particular input is the number of primitive operations or "steps" executed. It is convenient to define the notion of step so that it is as machineindependent as possible. For the moment, let us adopt the following view. A constant amount of time is required to execute each line of our pseudocode. One line may take a different amount of time than another line, but we shall assume that each execution of the ith line takes time c_{i} , where c_{i} is a constant. This viewpoint is in keeping with the RAM model, and it also reflects how the pseudocode would be implemented on most actual computers.
In the following discussion, our expression for the running time of INSERTIONSORT will evolve from a messy formula that uses all the statement costs c_{i} to a much simpler notation that is more concise and more easily manipulated. This simpler notation will also make it easy to determine whether one algorithm is more efficient than another.
We start by presenting the INSERTIONSORT procedure with the time "cost" of each statement and the number of times each statement is executed. For each j = 2, 3, . . . , n, where n = length[A], we let t_{j} be the number of times the while loop test in line 5 is executed for that value of j. When a for or while loop exits in the usual way (i.e., due to the test in the loop header), the test is executed one time more than the loop body. We assume that comments are not executable statements, and so they take no time.
The running time of the algorithm is the sum of running times for each statement executed; a statement that takes ci steps to execute and is executed n times will contribute cin to the total running time. To compute T(n), the running time of INSERTIONSORT, we sum the products of the cost and times columns, obtaining
Even for inputs of a given size, an algorithm's running time may depend on which input of that size is given. For example, in INSERTIONSORT, the best case occurs if the array is already sorted. For each j = 2, 3, . . . , n, we then find that A[i] ≤ key in line 5 when i has its initial value of j  1. Thus t_{j} = 1 for j = 2, 3, . . . , n, and the bestcase running time is
T(n) 
= 
c_{1}n c_{2}(n  1) c_{4}(n  1) c_{5}(n  1) c_{8}(n  1) 

= 
(c_{1} c_{2} c_{4} c_{5} c_{8})n  (c_{2} c_{4} c_{5} c_{8}). 