How do you calculate time complexity for insertion sort?

Answer 1

1.for j = 2 to length[A] c1 n

2. do key ¬ A[j] c2 n-1

3. //insert A[j] to sorted sequence A[1..j-1] 0 n-1

4. i ¬ j-1 c4 n-1

5. while i >0 and A[i]>key c5 Sum (j=2->n) tj

6. do A[i+1] ¬ A[i] c6 Sum (j=2->n) (tj -1)

7. i ¬ i-1 c7 Sum (j=2->n) (tj -1)

8. A[i+1] ¬ key c8 n -1

Sum j=2->n tj evaluates to (n(n+1)/2)-1 and j=2->(tj-1) evaluates to n(n-1)/2

thus the highest order term after droping constants becomes n2 thus the complexity is n2