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
4
-
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– Raymond Chen2019-02-07 06:52:04 +00:00Commented Feb 7, 2019 at 6:52
-
Maybe this will explain? metaltoad.com/blog/…Cat– Cat2019-02-07 06:55:16 +00:00Commented Feb 7, 2019 at 6:55
-
stackoverflow.com/questions/9358481/…Ng Sharma– Ng Sharma2019-02-07 06:56:04 +00:00Commented Feb 7, 2019 at 6:56
-
check this link your is clear.Ng Sharma– Ng Sharma2019-02-07 06:56:32 +00:00Commented Feb 7, 2019 at 6:56
Add a comment
|
2 Answers
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]
Comments
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.
