The Gateway to Computer Science Excellence
0 votes
354 views
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 by Active (3.7k points)
edited by | 354 views
0
What doubt you have in Insertion Sort?

1 Answer

+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).

by Junior (831 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,650 questions
56,238 answers
194,266 comments
95,872 users