A data structure is a way of arranging data in memory so certain operations on it are cheap; an algorithm is a sequence of steps that solves a problem, usually operating on a data structure. The reason interviews hammer on both together is that the "right answer" to almost every coding interview question is really a claim about cost: this operation touches every element, so it's O(n); this one only touches half the remaining search space each time, so it's O(log n). An interviewer asking "can you do better?" is asking whether you understand the cost model well enough to pick a structure that makes the expensive operation cheap. Get this right and you can reason about problems you've never seen before, because you're reasoning about the shape of the work, not pattern-matching to a memorized solution.
def linear_search(arr, target):
comparisons = 0
for i, x in enumerate(arr):
comparisons += 1
if x == target:
return i, comparisons
return -1, comparisonscomparisons counts work so the cost is visible, not assumed.Big-O is not a measure of time in seconds — it's a measure of how the number of basic operations grows as the input size n grows, ignoring constant factors and lower-order terms. "Basic operation" means something like a comparison, an arithmetic step, or an array access — one unit of work that takes roughly constant time regardless of n. Big-O (O) describes an upper bound: the algorithm never does asymptotically more work than this. Big-Omega (Ω) describes a lower bound: it never does asymptotically less. Big-Theta (Θ) is both at once — a tight bound, meaning the algorithm's growth rate is sandwiched between the same upper and lower shape.
This is the detail people get wrong: O(n) and Θ(n) are not "the same bound with different names" — O(n) is a claim you can make loosely (it's also technically correct to say linear search is O(n²), just a useless bound), while Θ(n) is a precise claim that the growth rate is exactly linear, no tighter and no looser. In casual interview speech people say "O(n)" when they mean Θ(n) — the exact growth rate — and that's fine as long as you know the difference when pushed. What Big-O does not measure: actual wall-clock time, memory addresses touched, or anything about a specific machine. It measures how the operation count scales.
Three different targets against the exact same algorithm on the exact same array produce wildly different comparison counts: 1, 7, or 10. That's the whole point of separating best/average/worst — the algorithm's code never changes, only the input's relationship to what you're looking for changes. Best case is a bound almost nobody cares about in interviews, because it describes lucky inputs, not the algorithm's real behavior. Average case matters for capacity planning (what will this cost typically, across many calls, assuming some distribution of inputs) but it depends on an assumption about the input distribution, which is often unstated and sometimes wrong.
Worst case is what interviewers default to because it's the only one that gives you a guarantee — a promise that holds no matter what the input looks like, including adversarial or unlucky inputs. If you tell a system "this query takes O(log n) on average," a pathological input (or an attacker who can choose inputs) can blow that up, and now your service is down. Worst-case bounds don't have that failure mode: they're true unconditionally. That's why "what's the worst case?" is almost always the real question behind "what's the time complexity?".
Space complexity has the same "growth as a function of n" definition as time complexity, but for memory instead of operations. It splits into two parts that get conflated constantly: input space is the memory the input itself already occupies (you didn't allocate it, it's just there), and auxiliary space is the extra memory your algorithm allocates on top of the input to do its job — a temporary array, a hash set, recursion stack frames. When someone says an algorithm is "O(1) space" or "in-place," they almost always mean O(1) auxiliary space — the input array itself is still sitting in memory, they just didn't allocate anything new proportional to n.
This distinction matters because it's easy to accidentally claim O(1) space for something that secretly isn't. Reversing an array with two pointers that swap in place is O(1) auxiliary space — no new memory scales with n. But a recursive version of the same reversal is O(n) auxiliary space, even though it looks like it's "not allocating anything," because each recursive call pushes a new stack frame, and there are n of them before the base case. Recursion depth is real memory, and interviewers expect you to count it.
def nested_loop_ops(n):
ops = 0
for i in range(n):
for j in range(n):
ops += 1
return opsops += 1. The outer loop picks a row, the inner loop walks all n squares in it (row i = 2 highlighted). Nested loops multiply: n × n.A nested loop where the inner loop also runs n times does n × n = n² total iterations — not 2n, because the loops aren't sequential, they're multiplied. Sequential loops add (a loop of n followed by a separate loop of n is n + n = 2n = O(n)); nested loops multiply (a loop of n containing a loop of n is n × n = O(n²)). The doubling of the counts above (4 → 16 → 64 → 256, each exactly 4× the last when n doubles) is the empirical signature of quadratic growth: double the input, and the work multiplies by 2² = 4, not by 2.
def double_recurse(n):
if n <= 0:
return 1
return double_recurse(n - 1) + double_recurse(n - 1)A function that calls itself once with n-1 (linear_recurse) builds a recursion "tree" that's really just a straight line — n frames deep, one call at each level, so it's O(n) total calls. A function that calls itself twice with n-1 (double_recurse, like a naive Fibonacci) builds an actual binary tree: level 0 has 1 call, level 1 has 2 calls, level 2 has 4 calls, and so on, doubling at each of the n levels. Summing a geometric series 1+2+4+...+2ⁿ gives 2ⁿ⁺¹−1 total calls — the demo output confirms it exactly (n=5 gives 63 = 2⁶−1). That's why doubling the recursive branching factor turns a fast O(n) algorithm into an exponential O(2ⁿ) one, even though both "just recurse to n-1."
Linear structures (arrays, linked lists, stacks, queues) arrange elements in a sequence — each element has at most one "next" and one "previous," and traversal has one natural order. Non-linear structures (trees, graphs, heaps) let an element connect to multiple others, so there's no single traversal order — you choose depth-first, breadth-first, or something problem-specific. This isn't just a taxonomy exercise: it predicts which operations are natural. "Find the next element" is trivial on a linear structure and often meaningless on a graph (next in what sense — by edge weight? by distance? by insertion time?).
An Abstract Data Type (ADT) is a specification of what operations are available and what they guarantee, deliberately silent on how they're implemented. A stack is an ADT: push, pop, peek, and "the last thing pushed is the first thing popped" — that's the whole contract. You can implement a stack with an array or with a linked list; both satisfy the ADT, but they have different performance profiles (array: fast access, occasional resize cost; linked list: no resize, extra pointer memory). When an interviewer asks "what data structure would you use," they're really asking you to pick an ADT for the required operations, then justify a concrete implementation for the required performance.
Two small demos: measuring best/average/worst case on a linear search, and counting operations directly for a nested loop and for linear vs doubling recursion, to see the growth patterns as real numbers instead of just formulas.
def linear_search(arr, target):
comparisons = 0
for i, x in enumerate(arr):
comparisons += 1
if x == target:
return i, comparisons
return -1, comparisons
arr = [5, 2, 8, 1, 9, 3, 7, 4, 6, 0]
idx, cmp = linear_search(arr, 5) # best case: first element
print(f"best case (target=5, arr[0]): found at {idx}, comparisons={cmp}")
idx, cmp = linear_search(arr, 0) # worst case: last element
print(f"worst case (target=0, arr[-1]): found at {idx}, comparisons={cmp}")
idx, cmp = linear_search(arr, 7) # average case: somewhere in the middle
print(f"average case (target=7, arr[6]): found at {idx}, comparisons={cmp}")
idx, cmp = linear_search(arr, 99) # not found: same shape as worst case
print(f"not found (target=99): found at {idx}, comparisons={cmp}")
# Output:
# best case (target=5, arr[0]): found at 0, comparisons=1
# worst case (target=0, arr[-1]): found at 9, comparisons=10
# average case (target=7, arr[6]): found at 6, comparisons=7
# not found (target=99): found at -1, comparisons=10
def nested_loop_ops(n):
ops = 0
for i in range(n):
for j in range(n):
ops += 1
return ops
for n in [2, 4, 8, 16]:
print(f"n={n:>3}: operations={nested_loop_ops(n):>4} (n^2={n*n})")
# Output:
# n= 2: operations= 4 (n^2=4)
# n= 4: operations= 16 (n^2=16)
# n= 8: operations= 64 (n^2=64)
# n= 16: operations= 256 (n^2=256)
calls = {"count": 0}
def double_recurse(n):
calls["count"] += 1
if n <= 0:
return 1
return double_recurse(n - 1) + double_recurse(n - 1)
for n in [1, 2, 3, 4, 5]:
calls["count"] = 0
double_recurse(n)
print(f"double_recurse(n={n}): total calls={calls['count']} (2^(n+1)-1={2**(n+1)-1})")
# Output:
# double_recurse(n=1): total calls=3 (2^(n+1)-1=3)
# double_recurse(n=2): total calls=7 (2^(n+1)-1=7)
# double_recurse(n=3): total calls=15 (2^(n+1)-1=15)
# double_recurse(n=4): total calls=31 (2^(n+1)-1=31)
# double_recurse(n=5): total calls=63 (2^(n+1)-1=63)linear_search returns the index and the comparison count, run on four targets: first element, last element, a middle one and a missing one. The counts (1, 10, 7, 10) are the best, worst, middle and not-found cases.nested_loop_ops counts inner-loop executions for n = 2, 4, 8, 16: exactly n² each time.double_recurse counts its own calls with a shared counter (calls["count"], a dict so the nested function can update it). The totals 3, 7, 15, 31, 63 match 2ⁿ⁺¹ − 1.Q: What's the difference between a data structure and an algorithm?
A: A data structure is an arrangement of data in memory that makes certain operations cheap (an array makes indexed access O(1); a sorted array makes binary search O(log n) possible). An algorithm is the sequence of steps that operates on a structure to solve a problem. They're inseparable in practice — the same algorithm can be fast or slow depending on which structure backs it, e.g. BFS is O(V+E) on an adjacency list but O(V²) on an adjacency matrix for a sparse graph.
Q: What does Big-O actually measure — time, or something else?
A: It measures how the count of basic operations (comparisons, swaps, visits) grows as input size n grows, not wall-clock time. Two O(n) algorithms can run at very different real speeds because Big-O drops constant factors; it only tells you the growth shape, e.g. that doubling n roughly doubles the work for O(n), or roughly quadruples it for O(n²).
Q: Why do we usually care about worst case over average case?
A: Worst case is an unconditional guarantee — true for every possible input, including adversarial ones — while average case depends on an assumed input distribution that may not hold in production, especially if an attacker or unusual data can force the bad case. A service that's "O(log n) on average" can still degrade to O(n) under the wrong input pattern, and that's the case you need to have planned for.
Q: What's the difference between O(n) and Θ(n)?
A: O(n) is an upper bound — the algorithm does at most on the order of n operations, but a looser bound like O(n²) would also technically be a true O statement. Θ(n) is a tight bound — it's both O(n) and Ω(n), meaning the growth rate is exactly linear, not just "no worse than" linear. In casual speech "O(n)" is often used to mean Θ(n); precise usage distinguishes them.
Q: Why is nested-loop complexity O(n²) and not O(2n)?
A: Because the inner loop runs its full n iterations for each of the outer loop's n iterations — the counts multiply, not add. O(2n) would be the cost of two separate, sequential n-loops. The demo above confirms this empirically: doubling n from 8 to 16 took operations from 64 to 256, a 4× increase (2²), which is the signature of squared growth, not the 2× increase linear growth would show.
Q: What's the time complexity of a function that calls itself twice with n-1?
A: O(2ⁿ). Each call spawns two more at n-1, forming a binary tree with n levels; the total number of calls is the geometric sum 1+2+4+...+2ⁿ = 2ⁿ⁺¹−1, which is O(2ⁿ). The demo's double_recurse(5) makes exactly 63 calls, matching 2⁶−1 exactly — this is the classic naive-Fibonacci trap, and the fix is memoization, which collapses the tree back down to O(n) by never recomputing a subproblem.
Q: What's the difference between time complexity and actual runtime?
A: Time complexity is an asymptotic growth-rate classification (O(n), O(n log n), ...) that ignores constants and hardware; actual runtime is wall-clock seconds on real hardware, affected by constant factors, cache behavior, branch prediction, and the actual value of n. An O(n²) algorithm can outrun an O(n log n) one for small n if its constant factor is small enough — insertion sort beats merge sort on tiny or nearly-sorted arrays despite the worse asymptotic class.
Follow-up: If two algorithms are both O(n), why can one be 100x slower in practice?
A: Big-O hides the constant factor and any lower-order terms — an algorithm doing 100n operations and one doing n operations are both O(n), but the first is roughly 100x slower for every n. Real differences like cache locality (contiguous array scans vs pointer-chasing through a linked list), branch mispredictions, and memory allocation overhead all live inside that hidden constant, which is exactly why Big-O is a tool for comparing growth, not a tool for predicting exact runtime.
Follow-up: Is an algorithm that's O(n) always better than one that's O(n log n)?
A: Not necessarily for the n values you'll actually see — Big-O comparisons only guarantee which one wins as n grows toward infinity. For small or bounded n, the O(n log n) algorithm can win if its constant factor is smaller, and in practice many "hybrid" library sorts fall back to a simpler O(n²) algorithm like insertion sort below some small threshold because it's genuinely faster there.
Follow-up: You said recursion depth is auxiliary space — does an iterative version of the same algorithm always use less memory?
A: Usually, if the iterative version doesn't need its own explicit stack — swapping array elements iteratively is O(1) auxiliary space, versus O(n) for a naive recursive version's call stack. But if you rewrite recursion as iteration using your own explicit stack data structure (common for DFS on a tree), you've just moved the O(n) space from the call stack to a heap-allocated stack — same asymptotic cost, different location, sometimes better constant factors because you avoid function-call overhead.
Big-O analysis is the wrong tool when n is small and bounded, or when constants dominate — in those regimes, a "worse" asymptotic algorithm can be the faster real choice, and premature optimization toward asymptotic complexity can waste engineering time on a bottleneck that was never the actual bottleneck. It's also the wrong lens alone for systems with real memory hierarchies: an O(n) algorithm that thrashes cache by chasing pointers can lose to an O(n log n) algorithm that stays cache-friendly by scanning contiguous memory. Use Big-O to reason about how a design will scale as data grows, then profile the actual system before trusting the asymptotic story to predict which of two "close enough" options is faster today.