Clever Geek Handbook

Why is the time complexity of inserting an array O (n) and not O (n + 1)?

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

At best, when the insert is in last place, the time complexity is O (1). I am assuming we are considering 1 for element insertion since no elements are being moved here. Worst case considering we need to move n elements and then insert a new element. Should the time complexity be O (n + 1)? n to move items and 1 to insert.

Help is greatly appreciated. Thank.

+1


source to share


1 answer


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



+4


source






More articles:


All Articles