Big O Runtime for Sorted Array Insert (Beginner)

Question

The Big O runtime for inserting an item into a sorted array is O(N)

However, I was wondering why it isnt O(N^2) because wouldnt you have to first find the correct index to place the inserted item which is O(N), then shift the rest of the data down by one to make room for this inserted item which is also O(N)?

Possible duplicate of [How to find time complexity of an algorithm](http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) — Bernhard Barker, May 21 '17 at 01:42

score 0 · Accepted Answer · answered May 21 '17 at 01:37

0

No, that's O(N) + O(N), which is still just O(N).

answered May 21 '17 at 01:37

Bill the Lizard

398,270
210
566
880

Big O Runtime for Sorted Array Insert (Beginner)

1 Answers1