Recognize O(1) push and pop
Updated
ADT push and pop are O(1) time (amortized for growing arrays). Peek, isEmpty, size (if stored) are O(1). If any of these walk the stack, the implementation is wrong for this skill.
What to focus on
n items already on the stack do not make push slower. The only linear push is push all of another collection, which is n operations, each O(1).
Worked examples
push
a = [4, 1, 9], push 8- one write
Result: O(1)
pop
a = [4, 1, 9], pop- one read
Result: O(1)
n pushes
a = [], push n values- n operations
- each O(1)
- total O(n)
Result: O(n) total, not O(1) for the loop
Try it
Write labelCost(op). op is "push", "pop", or "nPushes". Return the cost label. Do not call a loop of n pushes O(1). a = [4, 1, 9], push 8 → O(1). a = [4, 1, 9], pop → O(1). a = [], push n values → O(n) total, not O(1) for the loop.
The stack may be empty for the single push and pop. You may start from [] for a loop of n pushes. Values are integers.