Discussion on: Comprehensive Big O Notation Guide in Plain English, using Javascript

['Seun Somefun]

Very great article and explanation. One of the best so far.Quick question how are shift() and unshift() linear runtime complexities?

[Şahin Arslan]

Hey Oluwaseun, thanks!

Great question. To be able to make a comparison, let's take a look at push() and pop() methods first:

push() - Adds an item at the end of an array
pop() - Removes an item from the end of an array

They don't need to iterate whole array to make these changes, they only need to operate with one element with a known index - last one.
Previous indexes inside the array does not getting effected by this change.
That's why both are these having O(1) - Constant time complexity.

Now let's think about how shift() and unshift() operates:

shift() - Removes an item from the beginning of an array
unshift() - Adds an item or items from the beginning of an array.

Even they also target a known index, they work different. Because mutation takes place at the beginning of an array, which causes an index change for all other elements coming after. Let's take shift() for an example:

const array1 = [ 'a', 'b', 'c' ]

const firstElement = array1.shift()

console.log(firstElement) => Output: 'a'
console.log(array1) => Output: ['b', 'c']

You see, before shift(), 'b' was at index[1] and 'c' was at index[2].
Now their indexes have changed to index[0] and index[1] respectively.

Therefore we can say runtime to operate an index shift is directly linked to the length of array, so these methods are having Linear runtime complexity.

But again, you will find the perfect accurate answer by reading the source code of Javascript Engine you are dealing with, which is often V8:

github.com/v8/v8/blob/master/src/o...

[Mackenzie]

And this is where the distinction in memory between an array and a linked list comes in, I suppose, because sticking something on the front of a linked list should be constant like the push & pop. (Meanwhile, accessing within a linked list is linear.)

['Seun Somefun]

Oh so what makes shift() and unshift() O(n) is because of the change in the index they cause for elements in the array and not because they affect a single element at a known index?

[Şahin Arslan]

Yes, main reason is mutation place: beginning of an array. Adding or removing an element from start changes index order of all other elements coming after it.

['Seun Somefun]

Thanks Sahin

[Celeste]

this is a super important point :-) thanks!