Time Complexity of Insertion Sort

Worst case

Consider the array  5  4  3  2  1

Let ins be the element to be inserted.

Pass 1

ins = 4  

  5  5  3  2  1               Compare 4 and 5 & move 5 to right by 1 pos    
  j  i

  4  5  3  2  1
j    i

Pass 2

ins = 3

  4  5  5  2  1              Compare 3 and 5 & move 5 to right by 1 pos     
     j  i

  4  4  5  2  1              Compare 3 and 4  & move 4 to right by 1 pos
  j     i

  3  4  5  2  1                
j       i

Pass 3

ins  = 2     

     3  4  5  5  1            Compare 2 and 5 & move 5 to right by 1 pos
           j  i

     3  4  4  5  1            Compare 2 and 4 & move 4 to right by 1 pos
        j     i

     3  3  4  5  1            Compare 2 and 3 & move 3 to right by 1 pos
     j        i

     2  3  4  5  1            
   j          i

Pass 4

ins = 1   

   2  3  4  5  5              Compare 1 and 5 & move 5 to right by 1 pos
            j  i

   2  3  4  4  5              Compare 1 and 4 & move 4 to right by 1 pos
         j     i

   2  3  3  4  5              Compare 1 and 3 & move 3 to right by 1 pos
      j        i

   2  2  3  4  5              Compare 1 and 2 & move 2 to right by 1 pos
   j           i

   1  2  3  4  5              
  j            i

Time Complexity

Pass                Number of comparisons required      Number of movements required

1                         1                                        1

2                         2                                        2

3                         3                                        3

...                      ...                                      ...

...                      ...                                      ...

n-1                      n-1                                      n-1

So,total number of comparisons and movements required  
= 2(1 + 2 + 3 + ....... + n-1) 
= 2((n-1)*n)/2
= n*(n-1)
∈ O(n^2)

Lets prove how it is O(n^2)

We say f(n) = O(g(n)) , if c1*g(n)<=f(n)<=c2*g(n) for all n>=n0 

Constants c1 and c2 are positive real numbers
n0 = non negative integer    
f(n),g(n) = non negative functions of non negative arguments                                               

Take g(n) = n^2 and f(n) = n^2-n

c1*n^2<=n^2-n<=c2*n^2

We know 0<=n^2-n<=n^2 ,so take c1=0,c2=1 and above condition is satisfied 
for all n>=1 (n0=1 here).

Time complexity = O(n^2)

Best case

Consider the array  1   2   3   4   5

Pass                Number of comparisons required     Number of movements required

1                        1                                    0

2                        1                                    0

3                        1                                    0

...                     ...                                  ...

...                     ...                                  ...

n-1                      1                                    0

So,total number of comparisons and movements required  = n - 1

Time complexity = O(n)

If you want to prove that it belongs to O(n) you know the procedure.