CODEWITHSUNDEEP
sortingbig-ocomplexity-theoryinsertion-sort
Danny
Danny

Reputation: 233

Accounting for time complexity of array insertion

Given an insertion sort on an array where you do O(n) comparisons to find the index to insert at, then insert, would the time complexity be O(n^3)?

Since for each element (n), you iterate through the sorted list(n), then insert (n).

From what I understand, normal implementations don't have any insertions, only swaps which reduces it to O(n^2) since the item is placed in the correct location via swaps, rather than insertions.

Psuedocode for O(n^3) insertion sort:

for element in array
    find the correct location
    then insert in the correct location

Upvotes: 1

Views: 114

Answers (2)

user607464
user607464

Reputation: 23

You're very close to having the right answer, but the correct time-bound here is O(n2). enter image description here

enter image description here

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372724

You're very close to having the right answer, but the correct time bound here is O(n2).

You're correct that you have to visit each element of the array, so you're going to be doing something O(n) times. And what is that something? As you noted, you first find the insertion point (that takes time O(n)), and then you shift things down to make room (that also takes time O(n)). This means that the work done per element is O(n) + O(n) = O(n). In your analysis, you multiplied these two O(n) terms together, which is why you're overestimating the total.

Overall you're doing O(n) work O(n) times, so a good upper bound on the total work done is O(n2).

Upvotes: 1

Related Questions