I'm a bit uncertain of your characterization of the complexity of stacks. In the general sense, stacks, independent of a language implementation, don't have any particular complexity guarantees. In the context of JavaScript, I don't believe the language guarantees any kind of complexity bounds.
In other languages, like C++, a stack/vector provides push in amortized constant time, and subscript access in constant time.
Only if your stack is implemented as a linked list would you need O(N) random access.
I believe your comment is correct, though the wording may be a bit confusing for some people. I had to read it a couple of times before it made sense to me :)
You're right that the ecmascript specification doesn't seem to provide any specific guarantee. In practice, I think we can usually count on the fact that Array.prototype.push is O(1) amortized, since that's the big-O for adding an item to a hash map, which seems to be how arrays are implemented in javascript behind the scenes.
If I were to be pedantic, and you know how I love to be when it comes to complexity, hash maps don't have O(1) amortized push time. They have O(1) average-input (possibly amortized) push time. :)
I'm a bit uncertain of your characterization of the complexity of stacks. In the general sense, stacks, independent of a language implementation, don't have any particular complexity guarantees. In the context of JavaScript, I don't believe the language guarantees any kind of complexity bounds.
In other languages, like C++, a stack/vector provides push in amortized constant time, and subscript access in constant time.
Only if your stack is implemented as a linked list would you need O(N) random access.
I believe your comment is correct, though the wording may be a bit confusing for some people. I had to read it a couple of times before it made sense to me :)
You're right that the ecmascript specification doesn't seem to provide any specific guarantee. In practice, I think we can usually count on the fact that
Array.prototype.pushis O(1) amortized, since that's the big-O for adding an item to a hash map, which seems to be how arrays are implemented in javascript behind the scenes.If I were to be pedantic, and you know how I love to be when it comes to complexity, hash maps don't have O(1) amortized push time. They have O(1) average-input (possibly amortized) push time. :)
Sigh. Yes, I believe it’s both! 😅