Why stack push is O(1)
Updated
Push touches a constant number of slots: write the new top and bump size (or top index). It does not walk the buried values. Cost does not grow with n, except rare array growth.
What to focus on
Linked-list stacks insert at head: also O(1). Array stacks append: amortized O(1) if you double when full. Scanning the stack on every push would be a bug, not the ADT.
Worked examples
n = 3
a = [4, 1, 9], push 8- one write at the end
- size 3 → 4
Result: O(1)
n = 1
a = [7], push 3- same one write
Result: O(1)
n = 0
a = [], push 4- write the first slot
- still no walk
Result: O(1)
Try it
Write countPushWrites(a, x). a is the stack, written [bottom, ..., top]. x is the integer to push. Count writes for push. An implementation that scans the whole stack before pushing is not O(1). On [], [7], and [4, 1, 9], push does a constant number of writes.
Values are integers. You may push onto empty. Count the ADT writes, not rare growth copies.