In an unsorted array, why is lookup by index O(1) but lookup by a stored field O(n)?
answer
- Two different questions, same data
- One asks where, one asks which
- Unsorted order tells you nothing
- A miss must rule out everything
- n/2 is still linear
basics
~20 sAn index names a position, so the array reaches that element in one step without examining anything else. A stored field names no position, so an unsorted array must examine elements one by one — up to n of them.
solid answer
~50 sThese are two different questions asked of the same data. "Give me position 7" is answered by computing where position 7 lives and reading it — the work does not grow with how many records the array holds, so it is O(1). "Give me the guest named Ada" is answered by comparing records until one matches; an unsorted array stores no information about where a given value sits, so the only honest strategy is to walk it. That is O(n): about n/2 comparisons when the record is present and uniformly placed, and exactly n every time the record is absent, since you cannot declare a miss until you have ruled out the last element. The trap is assuming that because indexed access is constant time, everything about the array is fast — constant-time access only pays off once you already know the index.
go deeper
Be ready to state both costs and the reason for each in one breath: an index names a position, a value does not. Know that a failed search over unsorted data always examines every element.
Explain why average-case n/2 is still linear, and why the constant-time claim silently assumes the index is already known. Be able to say what extra information would make search cheaper.
Show you cost the whole operation, not the fast half of it. Point out that lookups by a non-positional key are where a flat array starts to hurt, and name what you would measure before adding an auxiliary structure.
Own the framing that access patterns, not structures, drive the choice: if reads are overwhelmingly by identifier, a positional array is the wrong storage, and the cost of the secondary structure that fixes it is memory plus a consistency obligation on every write.
## Two different questions A static array is a fixed-size run of equally sized slots, numbered `0` to `n-1`. Two very different retrievals get asked of it, and confusing them is the single most common cost error juniors make. **Retrieval by position** — "what is in slot 7?" — is answered arithmetically. The array knows where slot 7 is because slot positions are computable from the slot number; no element other than the target is touched. Doubling the number of records does not add a single step, so the cost is O(1): constant with respect to n. **Retrieval by content** — "which record has ticket-holder name Ada?" — is a *search*. In an unsorted array, the arrangement of elements carries no information about where any particular value is. Every slot is an equally plausible home for the record you want, so the only correct procedure is to look at slot 0, then slot 1, and so on, comparing as you go. Cost grows in step with n, so it is O(n). ## Counting the comparisons honestly Run the guest-list scenario: an event holds n guest records, each with a ticket number and a name, stored in arrival order. - **Hit, best case:** the record is in slot 0 — one comparison. - **Hit, worst case:** the record is in the last slot — n comparisons. - **Hit, typical case:** if the target is equally likely to be anywhere, about n/2 comparisons. - **Miss:** always exactly n comparisons. You may not report "not present" until every slot has been ruled out. Notice that n/2 and n differ only by a constant factor of two, and big-O deliberately ignores constant factors, so the typical case is still O(n). "On average it only scans half" is a true statement about the constant, not a different complexity class. Notice too that misses are the expensive case, which matters for real workloads: a membership check that usually fails pays the full n every time. ## Why the index has to already be in your hand The constant-time claim comes with a precondition that is easy to skip over: *you must know the index*. If your input is a name and you first scan to discover which slot holds it, you have already paid O(n); reading the slot afterwards is free by comparison. The cost of an operation is the cost of the whole operation, including how you obtained its arguments. The guest-list example makes the honest version visible. If tickets are numbered `0, 1, 2, …` in the order guests were registered, and the record for ticket k is deliberately stored in slot k, then "look up by ticket number" genuinely is O(1) — because the ticket number *is* the position. That only works while the identifiers stay dense and contiguous. Give tickets a random eight-digit code and the mapping evaporates: you cannot allocate slots for every possible code, so you are back to scanning, or to a different structure entirely. ## What changes the picture The reason an unsorted array must be scanned is a lack of *information*, not a defect of arrays. Impose structure and search gets cheaper: if the records are held in sorted order by the field you search on, the arrangement itself tells you which half of the array a value could be in, and sublinear search becomes possible (how that search is written, and its boundary conditions, is its own subject). Add an auxiliary structure that maps values to positions and lookups by that value become fast at the cost of memory and of keeping the map in step with the array. Both are trades, not free wins. ## Saying it correctly in an interview Say: indexed access is O(1) because the position is computed rather than searched, and it never inspects other elements; search over an unsorted array is O(n) because no element's location is implied by its value, so correctness demands examining each one until a match, or all of them to prove a miss. Avoid these two claims, which sound fluent and are wrong. First, "arrays are fast to search because they are contiguous" — contiguity affects the constant factor of a scan, not the number of elements the scan must consider. Second, "O(1) means fast" — O(1) is a statement about how cost responds to growth. A constant-time step with an expensive constant can lose to a linear scan of ten elements; asymptotics only decide the argument once n gets large.
- Is a failed search cheaper or more expensive than a successful one?More expensive, and predictably so. A successful search may stop early — on average around halfway if the target is uniformly placed. A failed search has no early exit in an unsorted array: you cannot report absence until the last slot has been compared, so every miss costs exactly n comparisons. Workloads dominated by negative lookups, such as duplicate checks that usually pass, therefore run at the worst case all the time.
- Guests have random eight-digit ticket codes rather than sequential numbers. Does lookup by ticket stay O(1)?No. Constant-time access needs the identifier to *be* the position. Sequential codes can be used as slot numbers directly; random eight-digit codes cannot, unless you are willing to reserve a hundred million slots. With sparse identifiers you either scan the array — O(n) — or maintain a separate structure mapping code to position, which buys speed with memory and with the work of keeping the mapping consistent on every insert and removal.
- Someone says the scan is O(n/2) on average, so it is faster than O(n). What do you say?That n/2 and n are the same complexity class. Big-O discards constant factors deliberately, because they do not change how cost responds to growth: doubling the guest count doubles both. The observation is still useful when comparing two linear strategies against each other — halving real work is real — but it is not a different class, and quoting it as O(n/2) signals confusion about what the notation measures.
A seat number on your ticket takes you straight to the seat. Finding a friend in the same hall by face means walking the rows until you spot them — or walking every row to be sure they never came.
saying these in an interview costs you the question
- Says arrays are fast to search because they are contiguous
- Claims average-case linear search is O(log n)
- Assumes a miss can exit the scan early on unsorted data
- Quotes O(1) access after paying an O(n) scan to find the index
- Treats holding a value as equivalent to holding a position
- Equates O(1) with fast rather than with growth-independent