The iterative version of insertion sort was explained here. Check it out, if you have not. In this post, we will analyze the time complexity of iterative insertion sort.

First, we will follow the standard assumption that each line of our code takes a constant time to execute. Let that constant time be * c*. Also, the size of our input array is

*.*

**n**The lines of code **inside** the *for* loop will execute atmost *n* number of time where *n* is the number of iteration of the *for* loop.

void insertionSort(int *a, int n){ // a is the input array. n is the size of the array int i, j, key; for(j=1;j<n;j++){ i = j-1; key = a[j]; while(i>=0 && a[i] < key){ a[i+1] = a[i]; i--; } a[i+1] = key; } }

The time taken for each line of the code in worst case scenario after the program has executed successfully is as follows.

The *for* statement itself will execute *n+1* times. Why? Because the for statement will run the comparison one more time. Same is valid for *while* loop.

Code | Time Taken |
---|---|

int i, j, key; | c |

for(j=1;j<n;j++){ | c(n+1) |

i = j-1; | c*n |

key = a[j]; | c*n |

while(i>=0 && a[i] < key){ | c*[2+3+4+. . .+(n-1)]+c |

a[i+1] = a[i]; | c*[2+3+4+. . .+(n-1)] |

i–;} | c*[2+3+4+. . .+(n-1)] |

a[i+1] = key; | c*n |

} | |

} | |

For simplicity we make the following further assumptions and simplifications. These assumptions are valid since our analysis is asymptotic and we are only considering higher order terms for the worst case scenario.

- c(n+1) is assumed to be equal to c(n)
- c*[2+3+4+. . .+(n-1)]+c = c(2+3+4+. . .n)
- c*[2+3+4+. . .+(n-1)] is assumed equivalent to c(2+3+4+. . .n)

Now, from basic maths, we know that,

$$2+3+4\ldots+n = \frac{\left(n(n+1)\right)}{2} – 1 = \frac{n^{2}+n-2}{2}$$

Finally, adding all the time taken we get. .

$$c+ cn+ cn + c(\frac{n^{2}+n-2}{2}) + c (\frac{n^{2}+n-2}{2}) + c (\frac{n^{2}+n-2}{2}) + cn$$

The highest order term in the above equation is *n ^{2}*. Therefore, asymptotic worst case time complexity of insertion sort will be

$$c+ cn+ cn + c(\frac{n^{2}+n-2}{2}) + c (\frac{n^{2}+n-2}{2}) + c (\frac{n^{2}+n-2}{2}) + cn = O(n^{2})$$

**Best Case Time Complexity of Insertion Sort**

Best case will occur when the given input array is already sorted. The time taken by each line will as follows:

Code | Time Taken |
---|---|

int i, j, key; | c |

for(j=1;j<n;j++){ | c(n+1) |

i = j-1; | c*n |

key = a[j]; | c*n |

while(i>=0 && a[i] < key){ | c*n |

a[i+1] = a[i]; | 0 |

i–;} | 0 |

a[i+1] = key; | c*n |

} | |

} | |

A similar evaluation like above will give is the time complexity as

$$\Omega(n)$$

which is the best case time complexity.

\[\]