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; Algorithms algorithms time-complexity sorting programming-in-c data-structures + – LavTheRawkstar asked Jan 12, 2017 recategorized Jul 6, 2022 by Lakshman Bhaiya LavTheRawkstar 808 views answer comment Share Follow See 1 comment See all 1 1 comment reply Devshree Dubey commented Jan 12, 2017 reply Follow Share What doubt you have in Insertion Sort? 0 votes 0 votes Please log in or register to add a comment.
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). IamRishabh answered Jan 12, 2017 IamRishabh comment Share Follow See all 0 reply Please log in or register to add a comment.