Why are push and pop O(1) on a stack while finding a specific value in one is O(n)?
answer
- think about which end the operations touch
- the top is the only reachable position
- no step depends on how many are stored
- searching uncovers elements one at a time
- constant per operation, linear per scan
basics
~20 sPush and pop touch only the top position, so each does a fixed amount of work however many elements are stored. A stack exposes no access below the top, so finding a value means uncovering elements one at a time: O(n).
solid answer
~40 sA stack is defined by its restriction, not by its storage. The only reachable position is the top, so `push` writes one slot and moves one index, `pop` reads one slot and moves it back, and `peek` reads one slot — none of that work scales with the number of stored elements, which is why all three are O(1). Search is a different story: the contract gives you no way to address the k-th element, so answering "is value v in here?" means popping (or scanning the backing storage) element by element, which is O(n) and, using only stack operations, destructive. The right summary is that a stack buys constant-time access to *one* end by giving up addressing everything else — it is not a fast container in general.
go deeper
Be ready to state the four operations, the LIFO rule, and why touching only the top makes each operation constant time. Then say plainly that search is O(n) because nothing lets you reach past the top.
Explain the constant-time claim in both realizations — one index move over contiguous slots, one reference move over linked nodes — and be precise that O(1) is per operation, so n pushes cost O(n).
Show you treat the narrow interface as a design decision: name what the restriction buys in invariants and cost predictability, and what it costs when the workload starts asking membership or positional questions.
Own the framing that choosing a stack is choosing to give up addressing. Be ready to argue when that restriction is worth enforcing across a codebase and when a team's repeated drain-and-restore workarounds mean the ADT was mismatched from the start.
## What a stack actually promises A stack is an abstract data type: a set of operations plus a rule about the order in which elements come back out. The operations are `push(x)` (add an element), `pop()` (remove and return the most recently added element), `peek()` (return that element without removing it), and an empty check. The rule is LIFO — last in, first out. Nothing in that definition mentions arrays, nodes, or memory. Two realizations can satisfy it and share the same cost profile for the core operations. ## Why the core operations are constant time In a contiguous-storage realization, the stack keeps the elements in adjacent slots plus one integer, `top`, tracking where the live region ends. `push` writes one slot and adjusts `top` by one. `pop` reads one slot and adjusts `top` back. Neither reads any other element, and neither loops. The work is the same whether the stack holds 5 elements or 5 million — that is exactly what O(1) means. In a linked-node realization, the stack keeps a reference to the node most recently added, and each node references the node beneath it. `push` allocates a node, points it at the current head, and moves the head. `pop` reads the head's value and moves the head to the node beneath. Again: a fixed number of steps, independent of depth. So the constant-time claim comes from the *restriction*, not from cleverness. Because the contract only ever names one position, an implementation only ever needs to touch one position. ## Why search is linear The same restriction that makes push and pop cheap is what makes everything else expensive. A stack offers no operation that names the k-th element, so there is no index arithmetic to jump anywhere. To decide whether a value is present, you must remove elements until you find it or the stack is empty — O(n) comparisons, and afterwards the stack is gone unless you pushed the removed elements onto a second stack and restored them. If the implementation lets you scan its backing storage directly, you still examine up to n elements; you have just avoided destroying the stack. Either way, membership is linear, and no ordering trick helps: the elements are ordered by *arrival time*, not by value, so there is nothing to halve and no sortedness to exploit. This is the point candidates most often get backwards. "Stack operations are O(1)" is a claim about the three operations the contract defines, not a claim about the container. Asking a stack a question it does not define — find, count, get by position, find the largest — costs linear time or requires a different structure entirely. ## Directions the claim does not run Several over-readings of O(1) are worth naming explicitly. - **O(1) is per operation, not per program.** Performing n pushes costs O(n) total. Constant per step never means constant in aggregate. - **O(1) is not "fast".** It says the cost does not grow with n. A constant-time operation with an expensive constant — say, allocating a node per push — can lose to a linear scan over a small, cache-friendly block. - **O(1) is an upper bound on the work of the defined operations, in a realization with somewhere to put the element.** A realization with a hard capacity must also define what happens when it is full, and that policy is part of the contract rather than part of the cost claim. - **`peek` is not a cheap `pop`.** Both are O(1); the difference is that one mutates and one does not. Reading the top in a loop without removing it does not advance you through the stack. ## The framing that answers the question in an interview Say it as a trade: a stack narrows the interface to one end, and in exchange every operation on that end is constant time and every invariant is trivial to state. If the problem needs to reach past the top — search it, index it, keep it ordered by value — the stack is the wrong ADT, and reaching for one anyway means paying O(n) for a question the structure was designed not to answer.
- Why does a stack deliberately forbid reaching below the top?The restriction is the feature. Limiting the interface to one end means every operation touches exactly one position, so the cost model and the invariants stay trivial and callers can reason about ordering without inspecting the contents. A structure that allows arbitrary positional access is a different ADT with a different, larger cost model — you should pick it deliberately, not drift into it.
- What does peek buy over pop, and is it just convenience?`peek` reads the top without mutating, so code that inspects the current element and may or may not consume it does not have to remove and re-push to restore state. That matters for correctness, not just ergonomics: a pop-then-restore pattern is a place where an early return or an error path leaves the stack short an element. Both operations still need the same empty check.
- If I need to search often, what does that tell me about my structure choice?That the stack is the wrong primary structure for that access pattern. Either keep the stack for its ordering and maintain a separate membership structure alongside it, or step back and ask whether ordering by arrival time is what the problem actually needs. Repeatedly draining and restoring a stack to answer membership is a signal the interface has been forced.
A stack is a spring-loaded plate dispenser: taking or adding the top plate is one motion whether the tube holds three plates or thirty, but finding the chipped plate means lifting every plate above it.
saying these in an interview costs you the question
- Says stacks are O(1) for all operations, including search
- Claims push is constant because stacks stay small
- Believes a stack keeps its elements sorted by value
- Thinks n pushes cost O(1) total, not O(n)
- Confuses peek with pop and loses the top element
- Assumes O(1) means faster than any linear operation