Example: what is time complexity of insertion sort  Time Complexity is :   If the inversion count is O ( n ) ,   then the time complexity of insertion sort is O ( n ) .   Some Facts about insertion sort :  1.  Simple implementation :  Jon Bentley shows a three - line C version ,  and  a five - line optimized version [ 1 ]  2.  Efficient for  ( quite )  small data sets ,  much like other quadratic sorting algorithms 3.  More efficient in practice than most other simple quadratic  ( i . e . ,  O ( n2 ) )   algorithms such as selection sort or  bubble sort 4.  Adaptive ,  i . e . ,  efficient for  data sets that are already substantially sorted :  the time complexity is O ( kn )  when each element in the input is no more than k places away from its sorted position 5.  Stable ;  i . e . ,  does not  change the relative order of elements with equal keys 6.  In - place ;  i . e . ,  only requires  a constant amount O ( 1 )  of additional memory space Online ;  i . e . ,  can sort a list a...