General doubt on calculating the Time complexity for the given Insertion Sort Algorithm in the worst and average case

Question

INSERTION-SORT (A, n) ⊳ A[1 . . n]

for (j ← 2 to len(A) )

{

key ← A[ j];

i ← j – 1 ;

                  while (i > 0 and A[i] > key)

                 {

                A[i+1] ← A[i];

                i ← i – 1;

                }

A[i+1] = key;

Comments

What doubt you have in Insertion Sort?

Answer 1

Here "j" loop will run "n-1" times and for "while" loop suppose you reach upto j=n and A[n] = smallest of all the value array  so we have to go checcking from A[N-1] to A[1] therefore in worst case inner loop will run "n-1" time.

so in worst case time complexity will be O( (n-1)(n-1) ) = O(n²).