in Algorithms recategorized by
673 views
0 votes
0 votes
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;
in Algorithms recategorized by
673 views

1 comment

What doubt you have in Insertion Sort?
0
0

1 Answer

1 vote
1 vote

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(n2).

Related questions