I was reading about runtime complexities of array operations and learned that...
- the ECMAScript specification does not mandate a specific runtime complexity, so it depends on the specific implementation / JavaScript engine / runtime behavior [1] [2].
Array.push()runs in constant andArray.unshift()in linear time for sparse arrays implemented by a hash-table like data structure [3].
Now I was left wondering whether push and unshift have the same constant respectively linear time complexity on dense arrays. Experimental results in Firefox/Spidermonkey confirm that:
Now my questions:
- Are there official docs or references confirming the observed runtime performance for Firefox/Spidermonkey and Chrome/Node/V8?
- Why has
unshiftnot been implemented with constant runtime similar topush(and e.g. maintaining an index offset; similar to perl arrays)?
