recategorized by
808 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;
recategorized by

1 Answer

1 votes
1 votes

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

1 votes
1 votes
1 answer
1
rahuldb asked May 7, 2017
12,232 views
Derive the best and worst case complexity of insertion sort algorithm?
1 votes
1 votes
2 answers
3
vishal chugh asked Jan 24, 2018
1,734 views
What is the worst case time complexity to find kth smallest element into an array of ‘n’ element?
8 votes
8 votes
2 answers
4