Why stack pop is O(1)
Updated
Pop reads the top and shrinks size by 1. It does not slide buried values down. Array pop is a decrement; list pop is delete-head. Both are O(1).
What to focus on
If your pop scans to find the top, the backing structure is wrong. Amortized notes apply to shrinking arrays, not to the ADT contract.
Worked examples
n = 3
a = [4, 1, 9], pop- read last slot
- size 3 → 2
Result: O(1)
n = 1
a = [7], pop- read the only slot
- size 0
Result: O(1)
n = 2
a = [4, 1], pop- read last slot
- size 2 → 1
Result: O(1)
Try it
Write countPopWrites(a). a is the stack, written [bottom, ..., top]. Count reads and writes for pop. Copying the rest into a new array on every pop is not O(1). On [4, 1, 9], [4, 1], and [7], pop does a constant number of reads and writes.
The stack is non-empty. Values are integers.