Why are push and pop O(1) on a stack while finding a specific value in one is O(n)?

## 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.