Deleting Array Element in js?

Question

As array in js are objects but deleting an array element has BigO O(n) whereas deleting an obj element has BigO O(1) ? Why ?

Pls let me know where i am doing wrong !

Thanks

It's O(n) if you need to renumber the subsequent elements. It's O(1) if you don't - you can just leave a hole. — Raymond Chen, Feb 07 '19 at 06:52
Maybe this will explain? https://www.metaltoad.com/blog/javascript-understanding-objects-vs-arrays-and-when-use-them-part-1 — Cat, Feb 07 '19 at 06:55
https://stackoverflow.com/questions/9358481/algorithm-the-time-complexity-of-deletion-in-a-unsorted-array — Ng Sharma, Feb 07 '19 at 06:56

score 1 · Answer 1 · answered Feb 07 '19 at 08:28

This not an obvious question. In object this is more clearer because delete operator has constant time of complexity, because you are deleting specific property or method and don't iterate over the object. Array is an object with ordered indexes and we are using for deletion method which iterating over array and delete item such as Array.prototype.splice():

let arr = [1,6,10,99,44]; //If you want delete 10 you have to iterate by 1,6 and 10

arr.splice(2,1); //arr = [1,6,99,44]

And above we have linear time of complexity (BigO(n)), but we can achieve a constant time for deletion item from array:

let arr = [1,6,10,99,44]; //If you want delete last item

arr.length = 4 //arr = [1,6,10,66]

Finally one tip, never use delete operator for array, such as delete arr[2], because length of the array is not changed and you get an array [1,6, empty,99,44]

score 0 · Answer 2 · answered Feb 07 '19 at 08:17

deleting an obj element has BigO O(1)

That is because objects in JS behave like hashmap

deleting an array element has BigO O(n)

That is because array is special object that keeps its elements on a chunk of memory one by one without free spaces between elements. After deleting an element with i index you should move all elements that had grater than i+1 indexes to fill the released space.

Deleting Array Element in js?

2 Answers2