2

I just started learning data structure and while going through array insertion I wondered why is time complexity of array insertion O(n) and not O(n+1) ?

In best case, when insertion is at the last place,the time complexity is O(1). I suppose we are considering 1 to insert the element as no elements are moved here. In worst case, Given that we have to move n elements and then insert the new element, Shouldn't the time time complexity be O(n+1) ? n for moving the elements and 1 for insertion.

Help is very much appreciated.Thanks.

Armaan Khan
  • 21
  • 1
  • 3

1 Answers1

10

Any function that is O(n) is also O(n+1), and vice versa. Lower-order terms are essentially ignored, so the +1 doesn't contribute anything meaningful.

chepner
  • 497,756
  • 71
  • 530
  • 681