Skip to content
Data Structures & Algorithms

Big-O Notation interview questions and answers

30 questions, 12 with code. About 2 h 34 min to read them all.

By TestLab · Updated

Plan for an interview
30 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

How does Big-O notation describe algorithm scalability?

Big-O notation describes an asymptotic upper bound on an algorithm’s resource usage as its input grows. It is commonly used to express time complexity, but it can also describe space complexity; it does not inherently mean average-case performance.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Formal Bounds

Big-O, Big-Omega, and Big-Theta describe different relationships between a measured function f(n) and a comparison function g(n).

Notation Meaning Formal condition
Big-O Upper bound f(n) ≤ c · g(n) for some constants c and n₀, when n ≥ n₀
Big-Omega Lower bound f(n) ≥ c · g(n) under the same conditions
Big-Theta Tight bound Both an upper and lower bound hold

For example, if an algorithm takes Θ(n) time, it is also technically in O(n²). Big-Theta is more informative because it identifies the tight bound.

Best, average, and worst cases are a separate classification:

  • Best case: fastest behavior for the most favorable input.

  • Average case: expected behavior over a defined input distribution.

  • Worst case: slowest behavior for any valid input.

For example, hash-table lookup is O(1) best and average case but O(n) worst case because of collisions.

Common Complexity Classes

Here, n is the number of input elements. Space is auxiliary space, excluding the original input unless stated otherwise.

Class Example Time Extra space
O(1) Read the first element O(1) O(1)
O(log n) Binary search O(log n) O(1)
O(n) Sum all elements O(n) O(1)
O(n log n) Merge sort O(n log n) O(n)
O(n²) Examine every pair O(n²) O(1)
O(2ⁿ) Recursively make two equal-sized choices O(2ⁿ) O(n) stack
O(n!) Recursively count permutations O(n!) O(n) stack

Deriving a Bound

Analyze the number of operations as n increases:

  1. Drop constants and lower-order terms: 3n + 20 becomes Θ(n).

  2. Sequential steps add: O(n) followed by O(n) is O(n).

  3. Nested loops multiply: n iterations containing n iterations is O(n²).

  4. Recursion uses a recurrence: For T(n) = 2T(n/2) + O(n), the result is Θ(n log n), which can also be derived with the Master Theorem.

Use Θ when claiming a tight bound; reserve Big-O when only an upper bound is needed.

Time, Space, and Amortization

  • Time complexity counts the operations performed by the algorithm.

  • Space complexity counts additional memory, including the recursion stack. State whether the input itself is counted.

  • Total space includes the input and any data structure that stores it.

  • Amortized complexity describes the average cost per operation over a sequence, not one arbitrary operation.

For example, appending to a dynamic array is O(n) in the worst case because resizing may copy every element. Across many appends, however, append is O(1) amortized because copying occurs only after enough elements have been added. The array uses O(n) total storage, and a resize may temporarily require O(n) additional space.

Common Pitfalls

  • Do not use O to mean “average case”; state the case explicitly.

  • Do not assume O(n) is tight when Θ(n) is known.

  • Include recursion-stack space in recursive algorithms.

  • Decide whether the input is included in the reported space.

  • Distinguish worst-case cost from amortized cost for operations such as dynamic-array append.

  • Explain assumptions, such as a sorted input for binary search.

  • Common follow-ups include analyzing recurrence relations, identifying dominant terms, and comparing an algorithm’s time and space trade-offs.

2

How do Big-O, Big-Omega, and Big-Theta differ?

Big-O provides an asymptotic upper bound, Big-Omega provides a lower bound, and Big-Theta provides a tight bound. They describe how an algorithm’s resource usage grows as the input size increases, rather than which case—best, average, or worst—is being considered.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Formal Definitions

For functions (f(n)) and (g(n)):

  • Big-O: (f(n) = O(g(n))) if positive constants © and (n_0) exist such that (f(n) le c g(n)) for every (n ge n_0). It states that (g(n)) is eventually an upper bound.

  • Big-Omega: (f(n) = Omega(g(n))) if (f(n) ge c g(n)) for all sufficiently large (n). It states that (g(n)) is eventually a lower bound.

  • Big-Theta: (f(n) = Theta(g(n))) if both (f(n) = O(g(n))) and (f(n) = Omega(g(n))). It means the bound is tight.

For example, if an algorithm takes (3n + 7) operations:

  • It is (O(n)).

  • It is also (O(n^2)), but that is a loose bound.

  • It is (Omega(n)).

  • It is (Theta(n)), because the bound is tight.

Cases and Common Complexity Classes

Best, average, and worst case are separate from the notation:

  • Best case: minimum cost for inputs of size (n).

  • Average case: expected cost under a specified input distribution.

  • Worst case: maximum cost for inputs of size (n).

An algorithm can be (Theta(n)) in every case while still having different constants. Linear search, for example, has best case (Theta(1)), average case (Theta(n)) under a uniform distribution, and worst case (Theta(n)).

Common class Representative operation Tight time bound Auxiliary space
(O(1)) Array index access (Theta(1)) (Theta(1))
(O(log n)) Binary search (Theta(log n)) (Theta(1))
(O(n)) Linear scan (Theta(n)) (Theta(1))
(O(nlog n)) Merge sort (Theta(nlog n)) (Theta(n))
(O(n^2)) Enumerating all pairs (Theta(n^2)) (Theta(1))
(O(2^n)) Enumerating all subsets (Theta(2^n)) (Theta(n))
(O(n!)) Enumerating all permutations (Theta(n!)) (Theta(n))

Deriving Complexities

  • Drop constants and lower-order terms: (5n^2 + 3n + 20) becomes (O(n^2)).

  • Sequential operations add: running an (O(n)) step followed by an (O(log n)) step gives (O(n + log n) = O(n)).

  • Nested operations multiply: an (O(n)) loop containing an (O(n)) loop gives (O(n^2)).

  • Recursive operations use a recurrence: for (T(n) = 2T(n/2) + Theta(n)), the Master Theorem gives (Theta(nlog n)).

  • Branching recurrences matter: (T(n) = 2T(n-1) + Theta(1)) gives (Theta(2^n)), whereas (T(n) = nT(n-1) + Theta(n)) gives (Theta(n!)).

Space and Amortized Analysis

Space complexity must state whether the input is counted:

  • Auxiliary space excludes the input but includes temporary variables, allocated collections, and the recursion stack.

  • Total space includes the input, auxiliary memory, and output.

For example, recursive merge sort uses (Theta(n)) auxiliary space because it stores merged lists and has an (O(log n)) recursion stack.

Amortized analysis averages costs across a sequence of operations. Dynamic-array append is amortized (Theta(1)), even though one individual append can take (Theta(n)) when the array resizes. Its storage is (Theta(n)), with potentially unused capacity.

Common Pitfalls

  • Do not use “Big-O” to mean “average case.”

  • Do not confuse a loose upper bound with a tight (Theta) bound.

  • Include recursion-stack usage when calculating auxiliary space.

  • Binary-search implementations commonly have off-by-one errors around empty lists and inclusive right bounds.

  • Python integers do not overflow, but factorials and permutation counts can overflow fixed-width integers in Java or C++.

  • Avoid mutating the input unless the algorithm explicitly permits it.

  • When extending the analysis to graph algorithms, include the visited set in space calculations.

  • Interviewers commonly follow up by asking you to derive a recurrence, distinguish amortized from worst-case cost, or explain why a particular bound is tight.

3

How do constants and lower-order terms affect Big-O analysis?

Big-O analysis ignores constant factors and lower-order terms when identifying an algorithm’s asymptotic growth class. For example, 3n + 5, 10n, and n are all O(n) because constants and lower-order terms do not change the function’s dominant growth rate.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Big-O, Big-Omega, and Big-Theta

  • Big-O (O(f(n))): An upper bound describing an asymptotic growth rate. For example, 3n + 5 is O(n) and also O(n²).

  • Big-Omega (Ω(f(n))): A lower bound. If an algorithm requires at least linear time, it is Ω(n).

  • Big-Theta (Θ(f(n))): A tight asymptotic bound. Since 3n + 5 grows proportionally to n, it is Θ(n).

  • Best, average, and worst case: These describe different execution scenarios and are separate from Big-O, Big-Omega, and Big-Theta. For example, hash-table lookup is best-case O(1), average-case O(1), and worst-case O(n).

Constants and lower-order terms affect actual runtime but not the asymptotic class. For example, 3n + 5 performs more work than n, but the difference disappears as n grows.

Common Complexity Classes

Growth Example Time reason Typical space
O(1) Accessing values[0] Constant number of operations O(1) auxiliary
O(log n) Binary search Halves the search range each iteration O(1) auxiliary
O(n) Scanning all elements Visits every element once O(1) auxiliary
O(n log n) Comparison sorting Roughly n levels, each processing O(n) items Up to O(n) auxiliary
O(n²) Checking every pair Runs a linear scan for each of n items O(1) auxiliary
O(2^n) Enumerating all subsets Each element has two choices O(2^n) for the output
O(n!) Counting factorial-order paths Number of possible orderings grows factorially O(n) recursion stack

These space figures use the usual convention: auxiliary space excludes the input and returned output. Including the input, an operation consuming an n-element list requires O(n) total space.

Deriving Complexity

  • Drop constants and lower-order terms: 5n² + 3n + 20 becomes O(n²).

  • Sequential steps add: scanning an array and then scanning it again is O(n) + O(n) = O(n).

  • Nested loops multiply: n iterations with n work inside gives O(n²).

  • Recursive algorithms: derive a recurrence such as T(n) = 2T(n/2) + O(n), then solve it directly or use the Master Theorem. This example produces O(n log n).

  • Short input caveat: lower-order terms can dominate for small inputs. A 3n + 100 algorithm can be slower than 4n at small values despite both being Θ(n).

Amortized and Space Analysis

A dynamic-array append has amortized O(1) time: most appends are constant-time, but an occasional resize copies all elements and costs O(n). A single append can therefore have worst-case O(n) time, while the sequence of appends has amortized O(1) time.

Space analysis must also count the call stack. A recursive function with depth n uses O(n) stack space even if it allocates no other data structures. Python’s default recursion limit is approximately 1,000, so deeper recursive solutions should use an explicit stack or a raised limit.

Common Pitfalls

  • Using Big-O for average case: Say “average-case O(1)” rather than calling average case “Big-O.”

  • Ignoring constants entirely: They do not change the class, but they can materially affect runtime.

  • Forgetting stack space: Recursive calls consume O(depth) space.

  • Assuming all inputs are sorted: Binary search requires sorted data unless the algorithm sorts it first.

  • Mutating input accidentally: Check whether the operation changes ordering or contents.

  • Confusing amortized and worst-case time: List append is amortized O(1) but can cost O(n) during resizing.

  • Common follow-up questions: “Can one function belong to multiple Big-O classes?”, “What is the tight bound?”, and “How would amortized analysis change this conclusion?”

4

How does amortized analysis balance costs across operation sequences?

Amortized analysis distributes the cost of a sequence of operations over those operations by bounding the total work and dividing it by the number of operations. Thus, one operation may occasionally cost O(n), while a sequence of operations can still guarantee O(1) amortized cost per operation.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Big-O, Big-Omega and Big-Theta

These notation families describe how a function grows, independently of best, average and worst input cases.

  • Big-O: An upper-bound description. For example, O(n²) is also technically O(n³).

  • Big-Omega: A lower-bound description.

  • Big-Theta: A tight bound matching both the upper and lower growth rates.

  • Best, average and worst case: Separate classifications based on inputs or sequences of operations. Amortized analysis is not synonymous with average-case analysis.

Common Complexity Classes

Class Example
O(1) Accessing array[index]
O(log n) Binary search in a sorted list
O(n) Scanning every element
O(n log n) Merge sort
O(n²) Comparing every pair of elements
O(2ⁿ) Generating all subsets of n elements
O(n!) Generating all permutations

Deriving Complexity

  • Drop constants and lower-order terms: 3n + 20 is tightly Θ(n) and therefore also O(n).

  • Sequential steps add: Two independent O(n) loops produce O(n + n) = O(n).

  • Nested loops multiply: An O(n) loop containing an O(n) loop produces O(n²).

  • Recursion: Derive a recurrence such as T(n) = 2T(n/2) + O(n), then use the Master Theorem where applicable.

  • Space: Count auxiliary allocations, persistent data structures, output storage, and the recursion stack.

In the table below, total space includes the structure’s stored data and output, while auxiliary space excludes those elements. Mutable input stored in the structure, such as a counter, is counted; a separate read-only input is excluded.

Amortized Examples

For m operations with total cost T, the amortized cost per operation is T / m. The goal is a bound that holds for every operation sequence, not merely for randomly distributed inputs.

Two common techniques establish such bounds:

  • Accounting method: Charge each operation its actual cost, save unused credit, and spend that credit to pay for later expensive operations.

  • Potential method: Define a potential value for the data structure and charge each operation its actual cost plus the change in potential. Summing these charges makes the potential terms telescope into a bounded total.

“Sequence-average” below means the average cost across repeated operations. It is not a probabilistic average over randomly distributed inputs.

Operation Best Single Sequence-Average Worst Single Amortized Bound Space
Dynamic-array append O(1) O(1) O(n) when resizing O(1) O(n) total storage; O(1) auxiliary beyond elements; no call stack
Binary-counter increment O(1) O(1) O(k) bit flips for a k-bit counter O(1) O(k) bits including the mutable counter; O(1) auxiliary; no call stack
Union-find with rank/size and path compression O(1) O(α(n)) O(log n) for one find O(α(n)) O(n) total for parent/rank data; an iterative find uses O(1) auxiliary stack space

The dynamic-array result comes from proportional resizing: although copying n elements occasionally takes O(n), the total copying work across n appends is O(n). Likewise, incrementing a binary counter flips all trailing ones, but fewer than two bits are flipped per increment on average.

Union-find’s α(n) is the inverse Ackermann function, effectively constant for practical input sizes. Its amortized guarantee requires both union by rank or size and path compression. With union by rank or size, the tree height is at most O(log n), so even a single find is bounded by O(log n).

Common Pitfalls

  • Do not describe Big-O as “average case.”

  • Do not hide an operation’s worst-case spike: state both O(n) worst-case append and O(1) amortized append.

  • Hash-table lookup averaging O(1) is an expected-time result, not automatically an amortized result.

  • list.pop(0) and list.insert(0, value) are O(n) because elements must be shifted.

  • Include recursion-stack space in recursive algorithms and state whether input storage is counted.

  • Watch for integer overflow in fixed-width languages when implementing counters or hash-table indices.

5

How do higher-order coefficients affect Big-O notation in practice?

Big-O notation is an asymptotic upper bound, so changing a polynomial’s positive leading coefficient does not change its growth class: 3n² + 5n + 2 and 100n² + 10n are both Θ(n²). Coefficients can still have a substantial effect on actual runtime, but Big-O does not distinguish constant factors.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Asymptotic Bounds

  • Big-O: f(n) ∈ O(g(n)) when constants c > 0 and n₀ exist such that f(n) ≤ c·g(n) for every n ≥ n₀. It is an upper bound, not necessarily the tightest one.

  • Big-Omega: f(n) ∈ Ω(g(n)) when f(n) ≥ c·g(n) eventually for some positive constant c. It is a lower bound.

  • Big-Theta: f(n) ∈ Θ(g(n)) when both bounds hold. It describes the tight growth rate.

  • Best, average, and worst case describe different execution scenarios and are separate from O, Ω, and Θ. For example, hash-table lookup has expected Θ(1) time under the standard uniform-hashing assumption, while its worst case can be Θ(n).

Effect of Coefficients

For a nonnegative polynomial

T(n) = aₖnᵏ + aₖ₋₁nᵏ⁻¹ + ... + a₀

the highest-degree term with a nonzero coefficient determines the asymptotic growth:

  • Changing aₖ to another positive constant preserves the Θ(nᵏ) class.

  • If aₖ becomes zero, that term disappears and the effective degree becomes lower.

  • Among implementations with the same asymptotic class, smaller leading coefficients often execute faster; 3n² performs roughly one-third the dominant arithmetic work of 100n².

  • Lower-order terms can matter for small or moderately sized inputs. In 3n² + 500n + 2, comparing the quadratic and linear terms gives 3n² = 500n at approximately n = 166.7: the linear term is larger below that point, while the quadratic term is larger above it.

Big-O class Time across cases Auxiliary space Example and reason
O(1) Best, average, worst: Θ(1) O(1) Array indexing performs a fixed number of operations.
O(log n) Best: Θ(1); average and worst: Θ(log n) O(1) Binary search repeatedly halves the search range.
O(n) Best: Θ(1); average and worst: Θ(n) O(1) Linear search may find the first item immediately but may inspect every item.
O(n log n) Python sorted: best Θ(n); average and worst Θ(n log n) O(n) Python 3.12 uses Timsort, which detects existing runs and needs temporary storage.
O(n²) Best, average, worst: Θ(n²) for all-pairs processing O(1) Every pair of nested-loop items is visited.
O(2^n) Best, average, worst: Θ(2^n) for enumerating all subsets O(n) A current subset or recursion path is retained.
O(n!) Best, average, worst: Θ(n!) for enumerating all permutations O(n) The recursion stack and current permutation require linear space.

These space bounds use the standard unit-cost model, exclude the given input and scalar results, and include returned collection allocations and recursion stacks. Python arbitrary-size integers can require additional bit-level storage beyond the corresponding fixed-width model.

Derivation and Amortized Analysis

  • Sequential steps: add their complexities.

  • Nested steps: multiply their complexities.

  • Recursion: derive a recurrence and solve it using substitution, a recursion tree, or the Master Theorem.

  • Constants and lower-order terms: drop them when deriving the asymptotic growth rate.

  • Dynamic-array append: amortized O(1). One append can take Θ(n) when resizing, but m appends take Θ(m) total time. The resulting array storage is O(n).

For 3n² + 5n + 2, the values at n = 10, 100, and 1,000 are 352, 30,502, and 3,005,002. The quadratic term increasingly dominates, illustrating why lower-order terms eventually become insignificant.

Common Pitfalls and Interview Tips

  • Do not use “Big-O” to mean average case; state the case and assumptions explicitly.

  • Do not assume coefficients are practically irrelevant—Big-O hides them, but benchmarks and crossover calculations can expose them.

  • Include recursion-stack space and state whether input and returned output are counted.

  • Watch for off-by-one errors in loop bounds and crossover calculations.

  • Factorial calculations can overflow fixed-width integers; Python integers avoid this but have larger bit-level storage costs.

  • Avoid mutating input unless mutation is intentional.

  • In graph extensions, forgetting a visited set can cause infinite loops around cycles.

  • Common follow-ups ask about tight bounds, average versus worst behavior, amortized append cost, recurrences, and the practical impact of constants.

6

How do probabilistic algorithms differ in Big-O from deterministic ones?

Big-O has the same meaning for probabilistic and deterministic algorithms; what changes is the guarantee used to state it—such as expected time, worst-case time, or high-probability time. A probabilistic algorithm may therefore report a smaller bound under a particular guarantee while retaining a larger adversarial worst case.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Big-O, Big-Omega, and Big-Theta

  • Big-O: An asymptotic upper bound. For example, (T(n)=O(f(n))) means the running time is no asymptotically larger than a constant multiple of (f(n)).

  • Big-Omega: An asymptotic lower bound, describing a minimum growth rate.

  • Big-Theta: A tight bound matching both the upper and lower bounds.

  • Best, average, and worst case: These describe different input or randomness distributions. Big-O, Big-Omega, and Big-Theta describe tightness; Big-O does not mean “average case.”

To derive a bound:

  • Drop constants and lower-order terms.

  • Add costs for sequential steps.

  • Multiply costs for nested loops.

  • Analyze recursive algorithms using a recurrence or the Master Theorem.

  • Use amortized analysis when individual operations vary. Dynamic-array append is amortized (Theta(1)), although one resize can take (Theta(n)); total space is (Theta(n)), including the array.

How Probability Changes the Bound

A probabilistic algorithm has a runtime that is itself a random variable. Common reporting styles include:

  • Expected-time bound: (mathbb{E}[T(n)] = O(f(n))).

  • High-probability bound: The runtime is (O(f(n))) with a stated confidence, such as probability at least (1-1/n^c).

  • Worst-case bound over all random outcomes: Often the same type of upper bound used for deterministic algorithms.

Two important algorithm categories are:

Category Correctness Runtime
Monte Carlo May fail within a stated error probability Usually has a firm upper bound
Las Vegas Always produces the correct result Often analyzed by expected or amortized time

Randomness does not automatically remove a bad worst case. It can make expected performance more stable across adversarial inputs, but an extreme random outcome may still cause poor runtime.

Representative Comparisons

Algorithm Best / Average / Worst Time Auxiliary Space Reason
First-pivot quicksort (Theta(nlog n)) / (Theta(nlog n)) for uniformly shuffled input / (Theta(n^2)) (O(log n)) expected, (O(n)) worst Sorted input repeatedly creates highly unbalanced partitions; the stack is included
Random-pivot quicksort (Theta(nlog n)) / (Theta(nlog n)) expected / (Theta(n^2)) (O(log n)) expected, (O(n)) worst Random pivots make expected partition sizes balanced, but extreme partitions remain possible
Hash-table lookup with chaining (Theta(1)) / (Theta(1)) expected under standard hashing assumptions / (Theta(n)) (Theta(1)) per lookup; (Theta(n)) total table space A good hash usually finds a short chain, while collisions can place every key in one chain

Thus, deterministic quicksort can take (Theta(n^2)) on sorted input, while randomized quicksort has expected (Theta(nlog n)) time on that input. Their adversarial worst cases remain (Theta(n^2)).

Common Complexity Classes

Auxiliary space below excludes the supplied input but includes recursion or explicit-stack storage.

Time Bound Example Space Reason
(O(1)) Array indexing (O(1)) Access uses a fixed number of operations
(O(log n)) Binary search (O(1)) Each comparison halves the search interval
(O(n)) Linear scan (O(1)) Every element may be inspected once
(O(nlog n)) Merge sort (O(n)) Logarithmic merge levels process (n) elements
(O(n^2)) Bubble sort (O(1)) Up to (n) passes each examine (n) elements
(O(2^n)) Enumerating all subsets (O(n)) There are (2^n) subsets and an (O(n)) recursion stack
(O(n!)) Brute-force search over all orderings (O(n)) There are (n!) candidate orderings

Interview Tips

  • State whether a bound is expected, high-probability, or worst-case.

  • Do not claim randomization eliminates worst-case behavior.

  • Include the call stack or explicit stack in space analysis and state whether input storage is excluded.

  • Distinguish amortized (Theta(1)) from worst-case (Theta(n)).

  • Mention whether the algorithm mutates its input and how randomness is seeded.

  • Common follow-ups ask about failure probability, confidence levels, deterministic fallbacks, and why the expected bound is valid.

7

What is the Big-O complexity of common array operations?

Big-O notation describes an asymptotic upper bound on how an algorithm’s time or space usage grows. For a random-access array, indexing takes O(1) time, while searching or shifting elements generally takes O(n) time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Asymptotic Bounds and Case Analysis

  • Big-O: An upper bound—eventually, f(n) ≤ c × g(n) for some constant c.

  • Big-Omega: A lower bound—eventually, f(n) ≥ c × g(n).

  • Big-Theta: A tight bound—eventually, f(n) is bounded above and below by constant multiples of g(n).

Best, average, and worst case describe different input or execution scenarios. They are separate from O, Omega, and Theta. For example, an O(n) worst-case bound does not mean the operation has average-case O(n) behavior. Amortized cost is a third, different notion: it bounds the total cost of a sequence of operations by the worst case of that sequence, so it is not an average case.

Common Complexity Classes

Bound Typical example
O(1) Reading an array element by index
O(log n) Binary search in a sorted array
O(n) Scanning an unsorted array
O(n log n) Comparison-based sorting
O(n²) Bubble sort in its worst case
O(2ⁿ) Enumerating all subsets
O(n!) Enumerating all permutations

The logarithm base does not change the asymptotic class: log₂ n, log₁₀ n, and ln n are all O(log n).

Array Operation Costs

These bounds assume a random-access array. A fixed-size array does not support append; dynamic arrays and Python lists do.

Operation Best case Average case Worst case Auxiliary space Why
Read/write by index O(1) O(1) O(1) O(1) Address is computed directly from the base pointer plus the index
Append to a dynamic array O(1) O(1) amortized (not an average case) O(n) during resizing O(1) extra slot; O(n) total storage Amortized O(1): resizes are rare and copy all n elements
Linear search O(1) O(n) O(n) O(1) Compares each element; the first element may match immediately
Binary search on sorted data O(1) O(log n) O(log n) O(1) Halves the search interval each step
Insert/delete in the middle O(n) O(n) O(n) O(1) for an in-place implementation The remaining elements must be shifted to open or close the gap
Copy a slice of length k O(k) O(k) O(k) O(1) auxiliary; O(k) for the output copy Each of the k elements is copied once
Python 3.12 sorted() O(n) O(n log n) O(n log n) O(n) Timsort detects existing runs, so sorted input costs O(n)

Auxiliary space excludes the original input array. Total space includes the input, any output, and the recursion stack when recursion is used. None of these examples is recursive, so no recursion-stack cost applies.

Deriving and Amortized Analysis

To derive a bound:

  1. Count the dominant primitive operations.

  2. Add costs for sequential steps.

  3. Multiply costs for nested loops.

  4. Take the maximum cost for alternative branches.

  5. Drop constants and lower-order terms when deriving a Big-O bound.

  6. For recursion, form a recurrence such as T(n) = aT(n/b) + f(n) and solve it, possibly using the Master Theorem.

Dynamic-array append is O(1) amortized, not O(1) for every individual append. Most appends are constant-time, but an occasional resize copies all n elements and costs O(n). Across m appends, the total work is O(m). This is a guarantee over a sequence of operations, not a probabilistic average over inputs.

Code Example

from bisect import bisect_left


def read_at(values: list[int], index: int) -> int:
    """Return the element at the specified index."""
    return values[index]


def contains_sorted(values: list[int], target: int) -> bool:
    """Search a sorted list using binary search."""
    position = bisect_left(values, target)
    return position < len(values) and values[position] == target


def sum_values(values: list[int]) -> int:
    """Return the sum of all values."""
    return sum(values)


def sorted_copy(values: list[int]) -> list[int]:
    """Return a sorted copy of the input list."""
    return sorted(values)


def bubble_sort(values: list[int]) -> list[int]:
    """Return an ascending copy using bubble sort."""
    result = values.copy()
    for end in range(len(result) - 1, 0, -1):
        swapped = False
        for index in range(end):
            if result[index] > result[index + 1]:
                result[index], result[index + 1] = (
                    result[index + 1],
                    result[index],
                )
                swapped = True
        if not swapped:
            break
    return result


print(read_at([10, 20, 30], 1))          # 20; O(1) time, O(1) auxiliary space
print(contains_sorted([1, 3, 5], 5))     # True; O(log n) time, O(1) auxiliary space
print(sum_values([10, 20, 30]))          # 60; O(n) time, O(1) auxiliary space
print(sorted_copy([3, 1, 2]))            # [1, 2, 3]; O(n log n) worst-case time, O(n) space
print(bubble_sort([3, 1, 2]))            # [1, 2, 3]; O(n²) worst-case time, O(n) output space

Common Pitfalls

  • Do not use “O(n)” as a synonym for average-case complexity.

  • Do not present amortized cost as average-case cost; they answer different questions.

  • Do not claim every array append is O(1); resizing makes the worst individual operation O(n).

  • Distinguish auxiliary space from total space, especially for sorting and slice operations.

  • Check whether the array is fixed-size or dynamically resizable.

  • Account for mutation, off-by-one loop errors, and integer overflow when reasoning about implementations in fixed-width languages.

  • Common interview follow-ups include choosing between linear and binary search, explaining amortized append, and analyzing the space used by sorting algorithms.

8

What is the Big-O space complexity of linked lists?

The Big-O space complexity of a linked list is O(n) because storing n elements requires n nodes, each containing a data field and a fixed number of link fields. This is separate from the auxiliary space used by an algorithm operating on the list.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Big-O and Related Bounds

  • Big-O describes an asymptotic upper bound on growth.

  • Big-Omega describes an asymptotic lower bound.

  • Big-Theta describes a tight bound where both upper and lower bounds have the same asymptotic growth.

Best, average, and worst cases describe how an operation behaves under different input or implementation conditions; they are separate from O, Omega, and Theta. The examples below use worst-case running time unless stated otherwise.

Class Example Time Auxiliary space
O(1) Access an array element by index O(1): one indexed lookup O(1): no additional storage
O(log n) Binary search a sorted array O(log n): each comparison halves the search range O(1) iteratively
O(n) Scan an array O(n): every element may be inspected O(1)
O(n log n) Merge sort O(n log n): log n merge levels processing n items O(n) for merged buffers
O(n²) Bubble sort O(n²): up to n comparisons per pass over n items O(1)
O(2^n) Enumerate all subsets O(2^n): there are 2^n subsets O(n) for the recursion stack
O(n!) Enumerate all permutations O(n!): there are n! orderings O(n) for the recursion stack

Linked-List Space

Assume each node has a constant-size payload and link fields. For a list of n elements:

  • Total storage: O(n) because the list contains n constant-sized nodes.

  • Input space: O(n) when the list itself is counted.

  • Iterative traversal auxiliary space: O(1) because only the current node and a few pointers are retained.

  • Recursive traversal auxiliary space: O(n) because the recursion stack can contain one frame per node.

These bounds do not differ between best, average, and worst cases. If only auxiliary space is counted, the existing linked list is excluded and an iterative traversal uses O(1).

Common operation costs are O(1) to access the head, O(n) to search for an arbitrary value, and O(1) to insert or delete after a suitable node is already known. Finding that position can require O(n) time.

Variants and Overhead

Variant Link fields per node Total space
Singly linked list 1: next O(n)
Doubly linked list 2: next and prev O(n)
Circular linked list 1: next O(n)

Doubly linked lists have twice as many link fields as singly linked lists, but the asymptotic space remains O(n). The head pointer uses O(1) space. If payload sizes vary, total storage also includes the size of the stored objects or values.

Deriving and Amortized Analysis

To derive time complexity:

  1. Drop constants and lower-order terms.

  2. Add costs for sequential steps.

  3. Multiply costs for nested operations.

  4. For recursion, derive a recurrence such as T(n) = 2T(n/2) + O(n), which gives O(n log n); use the Master Theorem when the recurrence has the required form.

An amortized bound averages operation costs over a sequence. For example, dynamically growing arrays such as Python lists have amortized O(1) append time: an individual append may resize the backing storage and cost O(n), but n appends perform O(n) total work. Their storage is O(n), including O(n) peak temporary space during resizing.

Common Pitfalls and Interview Tips

  • Do not confuse O(1) head access with O(1) space for the entire list.

  • Include pointer fields, object overhead, and payload storage when estimating real memory.

  • Include the recursion stack when analyzing recursive traversal.

  • Reversing a list in place uses O(1) auxiliary space but mutates the input.

  • Use a visited set when cycles are possible; ordinary acyclic traversal does not need one.

  • Watch for off-by-one errors when converting an index into a number of link traversals.

  • Fixed-width languages can overflow when calculating large indices or sizes; Python integers do not overflow at ordinary sizes.

  • Common follow-ups include iterative versus recursive traversal, cycle detection, sentinel versus head-based designs, and the time-space tradeoff of common operations.

9

How do sorting algorithms compare in Big-O time and space complexity?

Big-O notation describes an asymptotic upper bound on an algorithm’s growth rate. Sorting algorithms differ in their best, average, and worst-case running times, as well as the additional memory they require.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Big-O, Big-Omega, and Big-Theta

  • Big-O: An upper bound. If f(n) ∈ O(g(n)), then f(n) grows no faster than a constant multiple of g(n) beyond some input size.

  • Big-Omega: A lower bound describing minimum required growth.

  • Big-Theta: A tight bound matching both the upper and lower growth rates.

Best, average, and worst case describe the behavior of an algorithm under different input conditions. They are separate from O, Ω, and Θ. For example, quicksort has expected O(n log n) performance but an O(n²) worst case.

Sorting Algorithm Comparison

Space below means auxiliary space, excluding the original input but including recursion stacks and any newly allocated output.

Algorithm Best Time Average Time Worst Time Auxiliary Space
Insertion sort O(n) O(n²) O(n²) O(1)
Selection sort O(n²) O(n²) O(n²) O(1)
Bubble sort O(n) O(n²) O(n²) O(1)
Merge sort O(n log n) O(n log n) O(n log n) O(n)
Heapsort O(n log n) O(n log n) O(n log n) O(1)
Quicksort O(n log n) O(n log n) expected O(n²) O(log n) expected, O(n) worst
Counting sort O(n + k) O(n + k) O(n + k) O(n + k)

Here, k is the size of the integer value range. Counting sort is only appropriate for bounded-range integer keys.

  • Merge sort is stable and predictable, but requires additional memory.

  • Heapsort provides predictable O(n log n) time with constant auxiliary space, but is generally not stable.

  • Quicksort is usually fast in practice and often in-place, but depends heavily on pivot selection.

  • Insertion sort is efficient for small or nearly sorted arrays and is commonly used as a cut-off inside hybrid sorts.

Common Complexity Classes

Big-O Class Example
O(1) Accessing an array element by index
O(log n) Binary search in a sorted list
O(n) Scanning every list element
O(n log n) Merge sort
O(n²) Comparing every pair of elements
O(2^n) Enumerating all subsets
O(n!) Exhaustively considering every permutation

Deriving Complexity

  • Drop constants and lower-order terms: 3n + 5 becomes O(n).

  • Sequential steps add: scanning twice costs O(n) + O(n) = O(n).

  • Nested loops multiply: an n-element loop containing an n-element loop costs O(n²).

  • Recursion uses a recurrence: merge sort satisfies T(n) = 2T(n/2) + Θ(n), yielding Θ(n log n).

Merge sort tracing for [4, 1, 3, 2]:

  1. Split into [4, 1] and [3, 2].

  2. Split again into singleton lists.

  3. Merge [1, 4] and [2, 3].

  4. Merge them into [1, 2, 3, 4].

Dynamic-array append has a worst-case cost of O(n) when resizing, but an amortized cost of O(1): copying during occasional resizes gives O(m) total work for m appends. The array itself occupies O(n) storage.

Common Pitfalls

  • Do not describe O(n²) as “average case”; it is an upper-bound class.

  • Forgetting the recursion stack can understate quicksort’s or merge sort’s space.

  • Pivot selection can turn quicksort’s sorted-input behavior into its O(n²) worst case.

  • Confirm whether the implementation must be stable and whether extra memory is allowed.

  • Binary search requires sorted input.

11

What are the Big-O time and space complexities of hash table operations?

Hash-table lookup, insertion, and deletion are Θ(1) on average and O(n) in the worst case when many keys hash to the same bucket. The table occupies Θ(n) space; ordinary operations use O(1) auxiliary space, although resizing temporarily requires O(n) additional space.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Bounds and Case Analysis

Big-O, Big-Omega, and Big-Theta describe bounds, not probability:

  • Big-O: An asymptotic upper bound. f(n) = O(g(n)) means f(n) eventually grows no faster than a constant multiple of g(n).

  • Big-Omega: An asymptotic lower bound.

  • Big-Theta: A tight bound where both an upper and lower bound apply.

Best, average, and worst case describe how performance varies for a particular algorithm. For example, a hash-table lookup has a typical runtime of Θ(1), but a collision-heavy table can make the worst case Θ(n).

Hash Table Operation Complexities

Operation Best case Average/expected case Worst case Auxiliary space
Lookup Θ(1) Θ(1) Θ(n) Θ(1)
Insert or update Θ(1) Θ(1) Θ(n) Θ(1), or O(n) during resize
Delete Θ(1) Θ(1) Θ(n) Θ(1)
Resize Θ(n) Θ(n) Θ(n) Θ(n)
  • Hashing: Computing the bucket index takes O(1) time.

  • Collision handling: With separate chaining, the expected chain length is Θ(1) when the load factor is bounded and hashing distributes keys uniformly.

  • Worst case: If all n keys land in one bucket, an operation may inspect all n entries.

  • Amortized insertion: Growing the table by a constant factor gives Θ(1) amortized time per insertion. The individual insertion that triggers resizing still costs Θ(n).

  • Space convention: Auxiliary space excludes the original input. The hash table itself is counted separately and requires Θ(n) total storage. There is no recursion stack in the iterative implementation below.

For a conceptual trace, assume apple and banana both map to bucket 2:

  1. Insert apple: bucket 2 contains [apple].

  2. Insert banana: bucket 2 contains [apple, banana].

  3. Look up apple: the first chain entry matches, so the operation is O(1).

  4. If every key collided in one bucket, the same lookup could require Θ(n) comparisons.

Deriving Complexity and Growth Classes

To derive a bound, drop constants and lower-order terms, add sequential steps, and multiply nested loops. Recursive algorithms are analyzed with a recurrence or, when applicable, the Master Theorem.

Big-O class Example
O(1) Accessing values[index]
O(log n) Binary search on a sorted array
O(n) Scanning all array elements
O(n log n) Merge sort
O(n²) Bubble sort
O(2ⁿ) Enumerating every subset
O(n!) Enumerating every permutation

Code Example

This implementation demonstrates separate chaining, updates duplicate keys, and resizes when the load factor exceeds 75%.

from collections.abc import Hashable


def hash_table_operations(
    keys: list[Hashable],
) -> tuple[dict[Hashable, int], int | None, bool]:
    """Insert, update, look up, and delete keys in a chained hash table."""
    capacity = 8
    load_factor_threshold = 0.75
    buckets: list[list[tuple[Hashable, int]]] = [
        [] for _ in range(capacity)
    ]
    size = 0

    def resize() -> None:
        nonlocal buckets, capacity

        old_buckets = buckets
        capacity *= 2
        buckets = [[] for _ in range(capacity)]

        for bucket in old_buckets:
            for key, value in bucket:
                bucket_index = hash(key) % capacity
                buckets[bucket_index].append((key, value))

    def insert(key: Hashable, value: int) -> None:
        nonlocal size

        bucket_index = hash(key) % capacity

        # Lookup and update: O(1) expected, O(n) worst case.
        for item_index, (stored_key, _) in enumerate(buckets[bucket_index]):
            if stored_key == key:
                buckets[bucket_index][item_index] = (key, value)
                return

        buckets[bucket_index].append((key, value))
        size += 1

        # Resize: O(n) here, but O(1) amortized per insertion.
        if size > capacity * load_factor_threshold:
            resize()

    def lookup(key: Hashable) -> int | None:
        bucket_index = hash(key) % capacity

        # Lookup: O(1) expected, O(n) worst case.
        for stored_key, value in buckets[bucket_index]:
            if stored_key == key:
                return value

        return None

    def delete(key: Hashable) -> bool:
        nonlocal size

        bucket_index = hash(key) % capacity

        # Delete: O(1) expected, O(n) worst case.
        for item_index, (stored_key, _) in enumerate(buckets[bucket_index]):
            if stored_key == key:
                buckets[bucket_index].pop(item_index)
                size -= 1
                return True

        return False

    for position, key in enumerate(keys):
        insert(key, position + 1)

    lookup_value = lookup(keys[-1]) if keys else None
    deleted = delete(keys[0]) if keys else False

    snapshot = {
        key: value
        for bucket in buckets
        for key, value in bucket
    }
    return snapshot, lookup_value, deleted


result = hash_table_operations(["apple", "banana", "apple"])
print(result)  # ({'banana': 2}, 3, True)

Common Pitfalls

  • Do not use Big-O to mean “average case”; average case and asymptotic bounds are separate concepts.

  • Do not assume hashing guarantees O(1); collisions, poor load factors, and adversarial keys can cause Θ(n) operations.

  • Mention amortized rather than constant time when discussing resizing.

  • Count the hash table’s Θ(n) storage separately from the input and explicitly state whether temporary resize space is included.

  • The example handles empty input, one key, duplicates, negative numeric keys, and arbitrary input order. Graph-specific cases such as disconnected graphs and cycles do not apply.

  • Interviewers commonly follow up about collision resolution, load factors, resizing, deletion with tombstones, thread safety, and Python dict performance.

12

What are the Big-O complexities of BST and AVL tree operations?

Big-O notation describes an asymptotic upper bound on an algorithm’s resource usage. Tree-operation costs depend mainly on the tree’s height: a balanced AVL tree guarantees O(log n) height, while an ordinary binary search tree (BST) can degenerate to O(n).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Asymptotic Bounds

  • Big-O O(g(n)): An upper bound; f(n) grows no faster than a constant multiple of g(n) eventually.

  • Big-Omega Ω(g(n)): A lower bound; f(n) grows at least as quickly as g(n) eventually.

  • Big-Theta Θ(g(n)): A tight bound matching both the upper and lower bounds.

  • Best, average, and worst case describe different input scenarios. They are separate from O, Ω, and Θ; Big-O does not mean “average case.”

Common class Example Time Auxiliary space
O(1) Read an array element by index O(1) O(1)
O(log n) Search an AVL tree O(log n) O(1) iterative
O(n) Traverse every tree node O(n) O(h) recursive
O(n log n) Merge sort O(n log n) O(n)
O(n²) Compare every pair of elements O(n²) O(1)
O(2^n) Generate all subsets recursively O(2^n) O(n) stack
O(n!) Generate all permutations recursively O(n!) O(n) stack

Tree Operation Complexities

Here, n is the number of nodes and h is the height measured in edges.

Operation BST best BST average BST worst AVL best AVL average AVL worst Auxiliary space Reason
Search O(1) O(log n) O(n) O(1) O(log n) O(log n) O(1) iterative; O(h) recursive Follows one root-to-leaf path
Insert O(1) O(log n) O(n) O(log n) O(log n) O(log n) O(1) iterative; O(h) recursive Finds the insertion point and performs a constant amount of rebalancing work per visited level
Delete O(1) O(log n) O(n) O(log n) O(log n) O(log n) O(1) iterative; O(h) recursive Searches, restructures, and rebalances
Find minimum/maximum O(1) O(log n) O(n) O(log n) O(log n) O(log n) O(1) iterative; O(h) recursive Follows the leftmost or rightmost path
Full traversal O(n) O(n) O(n) O(n) O(n) O(n) O(1) iterative; O(h) recursive Visits every node exactly once

The BST average assumes a reasonably random insertion order. Sorted insertion produces a degenerate, chain-shaped BST. An AVL tree maintains a height difference of at most one between child subtrees, so its height remains O(log n) and its operations have guaranteed logarithmic bounds.

Space and Amortized Analysis

  • Iterative operation: O(1) auxiliary space because only the current node and a constant amount of state are stored.

  • Recursive tree operation: O(h) auxiliary space for the call stack.

  • AVL recursion: O(log n) stack space in the worst case.

  • Degenerate BST recursion: O(n) stack space in the worst case.

  • Input storage: The figures above are auxiliary-space bounds and exclude the tree’s stored input. Including the tree itself, storage is O(n) for either tree type.

  • Amortized analysis: Appending to a dynamic array is O(1) amortized because occasional O(n) resizing is spread across many operations. An individual resize can take O(n) time and O(n) peak space.

Deriving Complexities

  • Drop constants and lower-order terms: 3n² + 5n + 10 becomes O(n²).

  • Add sequential work: a loop followed by another loop costs O(n) + O(n) = O(n).

  • Multiply nested work: n iterations containing n work cost O(n²).

  • Analyze recursion with a recurrence such as T(n) = 2T(n/2) + O(n).

  • Use the Master Theorem for suitable divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n).

  • For AVL height, the minimum-node recurrence is S(h) = S(h-1) + S(h-2) + O(1). Fibonacci growth implies h = O(log n).

Common Pitfalls

  • Do not describe a BST as automatically logarithmic; balance must be guaranteed or reasonably likely.

  • Include the recursion stack when reporting recursive space complexity.

  • Define height consistently; this answer counts edges.

  • Watch for off-by-one errors when computing an empty tree’s height.

  • In fixed-width languages, be aware of integer overflow when calculating large sizes or heights.

  • Avoid mutating input structures unless the operation explicitly permits it.

  • Use a visited set for graph traversal; ordinary acyclic trees do not require one.

  • Recursive implementations may exceed Python’s default recursion limit on degenerate trees.

  • Common follow-ups ask about duplicate-key policies, deletion rebalancing, rotation cost, and implementing an AVL tree iteratively.

13

What are the Big-O complexities of graph traversal and shortest-path algorithms?

Big-O analysis describes how an algorithm’s time and space requirements grow with the graph size. For adjacency-list graphs, DFS and BFS take (O(V+E)), BFS finds unweighted shortest paths in the same bound, Dijkstra takes (O((V+E)log V)), Bellman–Ford takes (O(VE)), and Floyd–Warshall takes (O(V^3)).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Formal Bounds and Common Classes

  • Big-O: an asymptotic upper bound. (O(f(n))) means the cost is no greater than a constant multiple of (f(n)) for sufficiently large (n).

  • Big-Omega: an asymptotic lower bound, describing a minimum possible growth rate.

  • Big-Theta: a tight bound where the upper and lower bounds match.

  • Best, average, and worst case are separate from O, Omega, and Theta. They describe minimum, expected, and maximum inputs under a specified input distribution.

Complexity Example
(O(1)) Accessing values[index]
(O(log n)) Binary search on a sorted list
(O(n)) Scanning every array element
(O(nlog n)) Merge sort
(O(n^2)) Comparing every pair of elements
(O(2^n)) Enumerating all subsets
(O(n!)) Enumerating all permutations

Graph Cost Model

Let (V) be the number of vertices and (E) the number of edges.

  • Adjacency-list representation: stores (O(V+E)) input space.

  • Adjacency-matrix representation: stores (O(V^2)) input space and usually changes traversal costs to (O(V^2)).

  • Auxiliary space below excludes the graph representation itself. Recursion-stack space is included.

  • A traversal may cover only the source’s connected component, but its worst case processes all vertices and edges.

Algorithm Complexities

Algorithm Time Auxiliary Space Important Conditions
DFS (O(V+E)) (O(V)) Stack or explicit stack; not generally a shortest-path algorithm
BFS (O(V+E)) (O(V)) Finds shortest paths by edge count in an unweighted graph
Dijkstra (O((V+E)log V)) (O(V+E)) with a lazy heap Requires non-negative edge weights
Bellman–Ford (O(VE)) (O(V)) Supports negative edges; detects negative cycles
Floyd–Warshall (O(V^3)) (O(V^2)) Computes all-pairs shortest paths

Dijkstra can use (O(V)) auxiliary space with an indexed heap supporting decrease-key. A conventional lazy heapq implementation can retain outdated entries and therefore use (O(V+E)) auxiliary space.

For these deterministic algorithms, best, average, and worst cases usually have the same asymptotic order. Restricting traversal to one component can reduce actual work without changing the worst-case bound.

Common derivations include:

  • Sequential operations: add their costs.

  • Nested loops: multiply costs.

  • Repeated halving: (O(log n)).

  • Recurrence: solve equations such as (T(n)=2T(n/2)+O(n)), which gives (Theta(nlog n)).

  • Simplification: drop constants and lower-order terms, so (3n^2+5n+1) remains (O(n^2)).

  • Amortized analysis: dynamic-array append is amortized (O(1)), although an individual resize can take (O(n)).

Common Pitfalls

  • Do not use “Big-O” as a synonym for average-case complexity.

  • Do not assume DFS finds shortest paths; use BFS for unweighted shortest paths.

  • Never run Dijkstra with negative edge weights; use Bellman–Ford instead.

  • Remember that visited states prevent infinite processing of cycles.

  • Handle disconnected graphs: BFS and DFS can visit one component, while Dijkstra reports unreachable vertices as float("inf").

  • Recursive DFS may exceed Python’s recursion limit; use an explicit stack for large or deep graphs.

  • Check the representation: adjacency lists give (O(V+E)), while adjacency matrices generally give (O(V^2)).

  • In fixed-width languages, verify that path-cost arithmetic cannot overflow.

14

What are the time and space complexities of binary heap operations?

A binary heap stores elements in a complete binary tree, so its height is (O(log n)). Operations that restore heap order traverse at most that height, while accessing the root takes constant time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Big-O and Complexity Analysis

  • Big-O: an asymptotic upper bound on growth.

  • Big-Omega: an asymptotic lower bound.

  • Big-Theta: a tight bound that is both an upper and lower bound.

  • Best, average, and worst case describe different input or execution scenarios; they are separate from the O, Omega, and Theta classifications.

To derive complexity:

  • Drop constants and lower-order terms when finding a tight bound.

  • Add costs for sequential steps.

  • Multiply costs for nested loops.

  • Analyze recursive algorithms with a recurrence or the Master Theorem.

  • Bottom-up heap construction satisfies (T(n)=2T(n/2)+O(log n)), yielding (Theta(n)).

Heap Operation Complexities

The space column shows auxiliary space, excluding the existing heap storage. Including the heap itself, total space is (O(n)).

Operation Best Average Worst Auxiliary Space
Peek at root (O(1)) (O(1)) (O(1)) (O(1))
Insert (O(1)) Data-dependent; (O(log n)) upper bound before resizing (O(n)) with dynamic-array resize; otherwise (O(log n)) (O(1))
Extract root (O(1)) when no movement is needed (O(log n)) (O(log n)) (O(1))
Decrease key (O(1)) Data-dependent; (O(log n)) upper bound (O(log n)) (O(1))
Increase key (O(1)) Data-dependent; (O(log n)) upper bound (O(log n)) (O(1))
Delete arbitrary element (O(1)) (O(log n)) (O(log n)) (O(1))
Search for a value (O(n)) (O(n)) (O(n)) (O(1))
Build heap bottom-up (O(n)) (O(n)) (O(n)) (O(1))
Merge by copying (O(n+m)) (O(n+m)) (O(n+m)) (O(n+m))
Heap sort (O(nlog n)) (O(nlog n)) (O(nlog n)) (O(1)) iterative

Repeated heap insertion is (O(log n)) amortized. The list append is amortized (O(1)), while an individual resize can temporarily cost (O(n)). A recursive sift operation adds an (O(log n)) call stack; the iterative implementations below use (O(1)) stack space.

How the Core Operations Work

A binary heap stores children of index i at 2*i + 1 and 2*i + 2; its parent is at (i - 1) // 2.

  1. Insert: Append the value, then sift it upward while it is smaller than its parent.

  2. Extract root: Save the root, move the last element to the root, then sift it downward.

  3. Decrease key: Modify the element, then sift it upward.

  4. Build heap: Apply sift-down to every internal node in reverse index order.

For example:

  1. [5, 3, 8, 1, 2] becomes [1, 2, 8, 3, 5] after construction.

  2. Inserting 0 produces [0, 2, 1, 3, 5, 8].

  3. Extracting the root produces [1, 2, 8, 3, 5].

Common Complexity Classes

In increasing order of growth:

Class Example
(O(1)) Read values[0]
(O(log n)) Binary-search a sorted list
(O(n)) Sum every list element
(O(nlog n)) Comparison-sort all elements
(O(n^2)) Compare every pair of elements
(O(2^n)) Enumerate every subset
(O(n!)) Enumerate every permutation

Code Example

def _sift_down(heap: list[int], root: int) -> None:
    """Restore the min-heap property below root."""
    while True:
        left = 2 * root + 1
        right = left + 1
        smallest = root

        if left < len(heap) and heap[left] < heap[smallest]:
            smallest = left
        if right < len(heap) and heap[right] < heap[smallest]:
            smallest = right

        if smallest == root:
            return

        heap[root], heap[smallest] = heap[smallest], heap[root]
        root = smallest


def _sift_up(heap: list[int], index: int) -> None:
    """Restore the min-heap property above index."""
    while index > 0:
        parent = (index - 1) // 2
        if heap[parent] <= heap[index]:
            return

        heap[parent], heap[index] = heap[index], heap[parent]
        index = parent


def build_min_heap(values: list[int]) -> list[int]:
    """Build a min-heap in place: O(n) time, O(1) auxiliary space."""
    for root in range(len(values) // 2 - 1, -1, -1):
        _sift_down(values, root)
    return values


def insert_min(heap: list[int], value: int) -> None:
    """Insert a value: O(log n) amortized time, O(1) auxiliary space."""
    heap.append(value)
    _sift_up(heap, len(heap) - 1)


def peek_min(heap: list[int]) -> int:
    """Return the root: O(1) time and O(1) auxiliary space."""
    if not heap:
        raise IndexError("peek_min from an empty heap")
    return heap[0]


def extract_min(heap: list[int]) -> int:
    """Remove and return the root: O(log n) time, O(1) auxiliary space."""
    if not heap:
        raise IndexError("extract_min from an empty heap")

    minimum = heap[0]
    last = heap.pop()
    if heap:
        heap[0] = last
        _sift_down(heap, 0)
    return minimum


values = build_min_heap([5, 3, 8, 1, 2])
insert_min(values, 0)
print(values)                    # [0, 2, 1, 3, 5, 8]
print(extract_min(values))      # 0
print(values)                    # [1, 2, 8, 3, 5]

Common Pitfalls

  • Off-by-one errors: Use (i - 1) // 2 for the parent and 2*i + 1 for the left child.

  • Resize assumption: Insertion is not always worst-case (O(log n)) if the backing array must grow.

  • Integer overflow: In Java or C++, ensure priority values and index arithmetic use sufficiently wide types.

  • Input mutation: build_min_heap modifies its input; copy it first if mutation is undesirable.

  • Empty heaps: peek_min and extract_min must handle an empty heap explicitly.

  • Edge cases: Duplicate and negative priorities are valid; one-element and already-sorted inputs are also handled.

  • Unrelated graph concerns: Disconnected graphs, cycles, and visited sets do not apply to heaps.

15

What are space-time tradeoffs in algorithm design?

A space-time tradeoff occurs when an algorithm uses additional memory to perform fewer operations, or uses less memory at the cost of slower execution. The right choice depends on input size, available memory, query frequency, and whether average-case or worst-case performance matters most.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Big-O, Big-Omega, and Big-Theta

  • Big-O: An upper-bound notation. If g(n) is O(f(n)), then g(n) grows no faster than f(n) up to constant factors.

  • Big-Omega: A lower-bound notation. It describes a growth rate that an algorithm does not fall below asymptotically.

  • Big-Theta: A tight-bound notation. It means the algorithm’s running time grows at exactly the stated rate up to constant factors.

  • Best, average, and worst case are separate from these bounds. For example, hash-table lookup is O(1) average and worst-case O(n) under a worst-case collision pattern; “Big-O” alone does not mean average case.

To derive complexity:

  • Drop constants and lower-order terms.

  • Add costs for sequential operations.

  • Multiply costs for nested operations.

  • Analyze recursion with a recurrence. For T(n) = aT(n/b) + f(n), the Master Theorem compares f(n) with n^(log_b a).

Common Complexity Classes

Class Example Time reason Auxiliary space
O(1) Read an array element by index Direct address calculation O(1)
O(log n) Binary search a sorted list Each comparison halves the search range O(1)
O(n) Scan every array element Every element is visited once O(1)
O(n log n) Merge sort log n levels process n elements O(n)
O(n²) Check every pair of elements Two nested loops examine pairs O(1)
O(2^n) Enumerate every subset The number of subsets doubles O(n) stack
O(n!) Enumerate every permutation There are n! permutations O(n) stack

For binary search, the best case is O(1) when the first probed element matches; average and worst cases are O(log n).

Common Tradeoffs

Approach Time complexity Space complexity When to use
Linear search O(n) per query O(1) Small data or occasional queries
Hash-table index O(n) expected construction, O(1) expected lookup O(n) Many repeated lookups
Naive Fibonacci recursion O(2^n) O(n) stack Rarely appropriate beyond small inputs
Memoized Fibonacci O(n) O(n) table Repeated overlapping subproblems
Comparison sorting O(n log n) Algorithm-dependent Arbitrary comparable values
Counting sort O(n + k) O(k) Small, bounded integer range

The hash-table example is especially practical: paying O(n) memory once enables expected O(1) lookups afterward. Its expected performance depends on a good hash distribution; a worst-case collision-heavy lookup is O(n).

Space and Amortized Analysis

Unless stated otherwise, auxiliary space excludes the input but includes temporary arrays, data structures, and the recursion stack. Total memory usage adds the input’s O(n) storage.

Dynamic-array append is a classic amortized example:

  • A single append can take O(n) time when the backing array must grow.

  • Across m appends, resizing costs O(m) overall, so the amortized cost is O(1) per append.

  • The best individual append is O(1).

  • The array occupies O(m) total storage for m elements.

Code Example

def find_linear(values: list[int], target: int) -> int:
    """Return the first index of target, or -1 if it is absent."""
    # Worst-case time: O(n); auxiliary space: O(1).
    for index, value in enumerate(values):
        if value == target:
            return index
    return -1


def build_first_index(values: list[int]) -> dict[int, int]:
    """Map each value to its first position in values."""
    # Expected time: O(n); auxiliary space: O(n).
    index: dict[int, int] = {}
    for position, value in enumerate(values):
        index.setdefault(value, position)
    return index


def fibonacci_memo(n: int) -> int:
    """Return the nth Fibonacci number using memoization."""
    if n < 0:
        raise ValueError("n must be non-negative")

    # Time: O(n); auxiliary space: O(n).
    memo: dict[int, int] = {0: 0, 1: 1}
    for index in range(2, n + 1):
        memo[index] = memo[index - 1] + memo[index - 2]
    return memo[n]


# find_linear([3, -1, 3, 7], 3) -> 0
# build_first_index([3, -1, 3, 7]) -> {3: 0, -1: 1, 7: 3}
# fibonacci_memo(10) -> 55

These examples handle empty inputs and one-element inputs. Duplicates resolve to their first occurrence, negative values are supported, and sorted input does not change the hash-index approach. Graph-specific edge cases such as disconnected components and cycles do not apply.

Common Pitfalls and Interview Tips

  • Do not describe O(1) hash lookup without mentioning its average-case assumption and O(n) worst case.

  • Include recursion-stack memory when calculating auxiliary space.

  • Do not confuse amortized O(1) append with worst-case O(n) append.

  • Decide whether input storage counts before stating total memory usage.

  • Check whether a bounded value range is required before recommending counting sort or a dense lookup table.

  • Common follow-up questions ask about repeated queries, adversarial inputs, memory limits, and how the tradeoff changes as the input grows.

16

How do recursive and iterative solution complexities compare?

Big-O notation describes how an algorithm’s resource usage grows with input size. Recursive and iterative implementations of the same algorithm usually have the same asymptotic time complexity, but recursion adds call-stack space, while iteration may use constant space or an explicit stack.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Key Definitions

  • Big-O: An asymptotic upper bound. If an algorithm is O(f(n)), its usage is eventually no greater than a constant multiple of f(n).

  • Big-Omega: An asymptotic lower bound.

  • Big-Theta: A tight bound that is both an upper and lower bound.

  • Best, average, and worst case: These classify behavior under different input scenarios and are separate from Big-O, Omega, and Theta. Big-O does not mean “average case.”

  • Auxiliary space: Includes temporary variables, explicit stacks, and recursive call frames. It normally excludes the input and stored output; if input storage is counted, add its size to the auxiliary-space analysis.

Recursive vs. Iterative Comparison

Aspect Recursive solution Iterative solution
Time Determined by the algorithm; function calls add constant overhead Determined by the algorithm; loops usually have lower per-operation overhead
Auxiliary space Usually O(d), where d is the maximum recursion depth Often O(1), or O(d) when an explicit stack is required
Readability Natural for trees, graphs, and divide-and-conquer Often clearer for straightforward linear traversals
Scalability Can exceed Python’s default recursion limit of 1,000 nested calls Avoids recursion-depth limits
Constants Function calls and stack frames add overhead Loops generally avoid per-call overhead

The algorithmic work determines the time complexity. Equivalent recursive and iterative versions generally have the same asymptotic time bound.

  • Linear search: Best case is O(1) when the first element matches; average and worst cases are O(n) because up to all n elements may be examined. Recursive linear search uses O(n) stack space in the worst case, while iterative linear search uses O(1) auxiliary space.

  • Binary search on sorted data: Best case is O(1) when the middle element is inspected first; average and worst cases are O(log n) because each comparison halves the remaining range. Recursive binary search uses O(log n) stack space, while iterative binary search uses O(1) auxiliary space.

If one version adds memoization, dynamic programming, or changes the underlying algorithm, its complexity may differ—but that is an algorithmic change, not an inherent advantage of iteration.

Common Complexity Classes

The space bounds below are auxiliary-space bounds, excluding the input and any stored output.

Class Example Time and reason Auxiliary space and reason
O(1) len(values) # O(1) Constant metadata lookup O(1): only a constant amount of metadata is inspected
O(log n) bisect_left(sorted_values, target) # O(log n) Each comparison halves the search range O(1): only a few search variables are maintained
O(n) sum(values) # O(n) Every element is visited O(1): only an accumulator is maintained
O(n log n) sorted(values) # O(n log n) Sorting repeatedly divides and merges portions of the data O(n): temporary merge storage is required
O(n²) sum(1 for left in range(n) for right in range(left + 1, n)) # O(n²) There are n(n-1)/2 pairs O(1): the generator and loop counters use constant space
O(2^n) Recursively choose whether to include each item There are 2^n subset choices O(n): recursion depth is linear; output storage is excluded
O(n!) Recursively generate the permutations of n distinct items There are n! permutation choices O(n): recursion depth is linear; output storage is excluded

Deriving Complexity

  • Drop constants and lower-order terms: 3n + 10 becomes O(n).

  • Add sequential costs: O(n) followed by O(log n) is O(n + log n), which simplifies to O(n).

  • Multiply nested costs: O(n) work inside O(n) iterations is O(n²).

  • Analyze recursion with a recurrence: For T(n) = T(n - 1) + O(n), the solution is O(n²). The Master Theorem applies to suitable divide-and-conquer recurrences.

  • Include the call stack: A recursive function with maximum depth d uses O(d) auxiliary space. An equivalent explicit stack also uses O(d).

  • Analyze amortized operations: Dynamic-array append is amortized O(1). An individual append can cost O(n) during resizing, but resizing occurs infrequently enough that the amortized cost per append is constant. The array’s own storage is O(n).

Example Walkthrough

For the input [1, -2, 3]:

  1. The recursive version reads 1, -2, and 3, then reaches its base case returning 0.

  2. While unwinding, it computes 3 + 0 = 3, then -2 + 3 = 1, then 1 + 1 = 2.

  3. The iterative version starts with total = 0; it changes to 1, then -1, then 2.

  4. Both therefore return 2 in O(n) time. The recursive version uses O(n) stack space in the worst case, while the iterative version uses O(1) auxiliary space.

Both approaches handle empty input, one element, duplicates, and negative values.

Common Pitfalls

  • Do not claim recursion is always asymptotically slower; equivalent implementations commonly have the same time complexity.

  • Do not omit recursive stack frames or the memory required by an explicit stack.

  • Do not confuse an average-case result with Big-O itself.

  • Watch for off-by-one errors in base cases and loop bounds.

  • In fixed-width languages, large accumulators can overflow; Python integers do not have this limitation.

  • Avoid mutating the input unless the algorithm and interface explicitly permit it.

  • Graph traversals need a visited set to prevent cycles from causing infinite recursion.

  • Common follow-up questions include amortized analysis, recursion-depth limits, converting recursion to iteration, and analyzing divide-and-conquer recurrences.

17

Big-O implications of horizontal versus vertical scaling

Big-O describes how an algorithm’s resource usage grows with input size; horizontal or vertical scaling changes available capacity and distribution of work, but does not automatically change the algorithm’s asymptotic complexity.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Big-O, Big-Omega, and Big-Theta

  • Big-O: An asymptotic upper bound. T(n) = O(f(n)) means T(n) is bounded above by a constant multiple of f(n) beyond some input size.

  • Big-Omega: An asymptotic lower bound, describing a minimum growth rate.

  • Big-Theta: A tight bound, meaning f(n) provides both matching upper and lower bounds.

  • Best, average, and worst case are separate from O, Ω, and Θ. For example, hash-table lookup is O(1) best, O(1) average with good hashing and load management, and O(n) worst because of collisions. Its lookup uses O(1) auxiliary space, while the table itself occupies O(n) space.

  • O(1) means the upper bound does not grow with n; it does not imply every individual operation has identical execution time.

Common Complexity Classes

Class Typical example Best / average / worst time Auxiliary space and reason
O(1) Array index access O(1) / O(1) / O(1) O(1); direct offset access and no extra storage
O(log n) Iterative binary search O(1) / O(log n) / O(log n) O(1); each comparison halves the search range
O(n) Linear search O(1) / O(n) / O(n) O(1); it may scan every element
O(n log n) Standard merge sort O(n log n) / O(n log n) / O(n log n) O(n); merging needs a temporary array
O(n²) Bubble sort O(n) / O(n²) / O(n²) O(1); nested comparisons can examine every pair
O(2ⁿ) Full binary decision tree O(2ⁿ) / O(2ⁿ) / O(2ⁿ) O(n) recursion stack for a depth-n traversal
O(n!) Enumerating permutations with constant-time transitions O(n!) / O(n!) / O(n!) O(n) recursion stack; materializing every full permutation can add an O(n) factor

The average-case search bounds assume a uniformly random target; other distributions can differ. Auxiliary space excludes the input but includes the recursion stack. If an array containing n elements is counted, total storage is auxiliary space plus O(n).

Horizontal Versus Vertical Scaling

Let the original workload require O(f(n)) time and O(g(n)) auxiliary space on one server.

  • Vertical scaling: Time remains O(f(n)), and auxiliary space remains O(g(n)) on that server. Faster hardware or more memory improves capacity and constants but does not change the asymptotic bound.

  • Horizontal scaling with partitioned work: For an O(n) workload divided evenly across s servers, ideal per-server work is O(n/s), while aggregate work remains O(n). Per-server auxiliary space is approximately O(g(n)/s), plus coordination overhead.

  • Horizontal scaling with replicated data: Each server retains O(n) data, giving O(sn) aggregate storage. An operation requiring a complete scan can still take O(n) per server.

  • Horizontal scaling with sharded data: Each server stores approximately O(n/s) data, while aggregate data remains O(n). Cross-shard queries may cost more than a local query.

If s is constant, O(n/s) remains O(n): horizontal scaling gives only a constant-factor improvement. If s = Θ(n), ideal partitioning assigns O(1) work per server, although network and coordination costs may prevent that from becoming end-to-end latency. An O(n²) algorithm partitioned across s servers can have ideal latency O(n²/s), but its aggregate work remains O(n²).

Coordination cost depends on the protocol and workload; it may be O(s), higher-order in s, or dominated by cross-shard data movement. Amdahl’s Law also shows that a fixed serial portion limits achievable horizontal speedup.

Derivation and Amortized Analysis

  • Sequential steps: Add their complexities; two O(n) steps produce O(n).

  • Nested loops: Multiply them; an O(n) loop containing an O(n) loop produces O(n²).

  • Drop constants and lower-order terms: O(n² + n + 100) simplifies to O(n²).

  • Recursion: Derive a recurrence such as T(n) = 2T(n/2) + O(n), then solve it directly or apply the Master Theorem when its conditions hold.

  • Dynamic-array append: Amortized O(1) because occasional O(n) resizing is spread across many O(1) appends. One append can take O(n) in the worst case.

  • Dynamic-array storage: O(n), including allocated capacity; a resize may temporarily require O(n) additional space.

Common Pitfalls

  • Do not use Big-O to mean average case; Big-O is an upper bound.

  • Do not claim horizontal scaling automatically improves asymptotic complexity.

  • Distinguish per-server latency, aggregate work, throughput, and storage.

  • Include the recursion stack and state whether input storage is counted.

  • In algorithm implementations, watch for off-by-one errors, integer overflow in fixed-width languages, accidental input mutation, and forgetting a visited set.

  • A common interview follow-up is whether the design still works after a server failure. Horizontal scaling can improve availability, but it does not automatically provide consistency or fault tolerance.

18

What is the Big-O complexity of database indexing and query retrieval?

Big-O notation provides an asymptotic upper bound on resource growth. A database index often reduces lookup to O(log n) with an ordered B-tree, but the complete query may cost more because it can also filter rows, fetch table records, sort results, perform joins, and transfer data.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Formal Bounds and Common Classes

  • Big-O: An asymptotic upper bound. If an algorithm is O(n log n), its cost does not grow faster than that bound for sufficiently large n.

  • Big-Omega: An asymptotic lower bound.

  • Big-Theta: A tight bound where matching upper and lower bounds exist. For example, worst-case balanced B-tree navigation is Θ(log n).

  • Best, average, and worst case describe input or execution conditions; they are separate from O, Ω, and Θ.

Class Growth Example
O(1) Constant Array element access
O(log n) Logarithmic Balanced B-tree search
O(n) Linear Full table scan
O(n log n) Linearithmic Sorting n records with a comparison sort
O(n²) Quadratic Nested-loop join without usable indexes
O(2^n) Exponential Enumerating every subset
O(n!) Factorial Enumerating every permutation

Database Indexing and Retrieval Costs

The following assumes n rows, constant-width keys, and constant-time key comparisons. Auxiliary space excludes the original input and returned result set but includes the call stack.

Operation Best Average Worst Space
Hash-index equality lookup O(1) O(1) O(n) with severe collisions O(1) auxiliary; O(n) index storage
B-tree exact lookup O(1) if found at the root O(log n) O(log n) O(1) iterative auxiliary or O(log n) recursive stack; O(n) index storage
B-tree range retrieval O(log n + k) O(log n + k) O(log n + k) O(1) iterative auxiliary; O(k) output; O(n) index storage
Full table scan O(n) for a nonempty table O(n) O(n) O(1) when streamed; O(n) if materialized
Nested-loop join without usable indexes O(m × n) O(m × n) O(m × n) O(1) streaming auxiliary; up to O(m × n) materialized output

Additional costs include:

  • Index construction: Conventional B-tree construction generally takes O(n log n) time and O(n) index space. Bulk-loading pre-sorted data or using vendor-specific build algorithms can change the constants and sometimes the asymptotic work.

  • Index maintenance: A B-tree insert, update, or delete requires O(log n) tree work. Hash-index maintenance is O(1) average and O(n) worst case with severe collisions.

  • Complete retrieval: For a non-covering index, finding k matching index entries does not eliminate the cost of fetching their table rows; random row lookups can add up to O(k log n) work.

  • Sorting: ORDER BY without an ordered index commonly adds O(n log n) comparison work, but adaptive sorts, presorted inputs, external sorts, and top-N strategies can be faster.

  • Early termination: A query such as LIMIT 1 may take O(1) if the first row qualifies, but it may still take O(n) if no row qualifies.

Thus, O(log n) index navigation does not automatically imply an O(log n) complete query. Cache behavior, page size, index fanout, clustering, predicate selectivity, joins, and network or disk transfer also affect latency.

Deriving, Amortized, and Space Analysis

  • Sequential operations: Add their costs; O(log n) navigation followed by O(n) filtering gives O(n).

  • Nested operations: Multiply their costs; an O(m) outer loop containing O(n) inner work gives O(m × n).

  • Recursion: Express the cost as a recurrence, such as T(n) = 2T(n/2) + O(n), and solve it with substitution, the Master Theorem, or another recurrence method.

  • Amortized analysis: Dynamic-array append is best-case O(1), average-case O(1), and worst-case O(n) for one append, but O(1) amortized across a sequence because occasional resizing is spread across many appends.

  • Stack space: Recursive traversal uses O(h) stack space, where h is the tree height. For a balanced tree, h = O(log n); an iterative traversal generally uses O(1) stack space.

Worked Example

Suppose a table contains one million rows and has a useful B-tree index.

  1. An equality search navigates from the root toward a leaf, requiring O(log n) comparisons.

  2. If one row matches, fetching that row adds constant work, so the lookup remains O(log n) overall.

  3. If a range returns ten rows, index traversal plus output costs O(log n + 10).

  4. If the index does not cover the required columns, ten table-row lookups can add as much as O(10 log n).

  5. Without a usable index, the engine may inspect up to O(n) table rows.

Common Pitfalls

  • Do not use “average case” as a synonym for Big-O; case analysis and asymptotic bounds are separate.

  • Do not assume O(log n) index navigation describes the entire query.

  • Low-selectivity predicates can make an index scan plus row lookups slower than a sequential scan.

  • Off-by-one errors commonly affect range boundaries and whether an upper bound is inclusive.

  • In fixed-width languages, integer overflow can affect hash calculations and row-count estimates.

  • Avoid mutating sorted inputs when applying algorithms that require sorted order.

  • A visited set is required for graph traversals, not ordinary index lookups.

  • Common follow-ups cover index selection, covering indexes, write amplification, range scans, joins, and how selectivity changes the optimizer’s estimated cost.

19

How do caching layers affect system Big-O performance?

Caching layers reduce repeated computation by serving requests from a fast storage tier instead of recomputing results or retrieving them from slower backing services. They usually improve average-case performance and can reduce total asymptotic work, but they do not change the complexity of an individual cache miss.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Big-O Fundamentals

Big-O notation describes an asymptotic upper bound on resource growth as input size increases. Related bounds are:

  • Big-O: an upper bound, such as O(n).

  • Big-Omega: a lower bound, such as Ω(n).

  • Big-Theta: a tight bound where both bounds apply, such as Θ(n).

Best, average, and worst case describe behavior under different input distributions or conditions. They are separate from the bound notation: an operation can have an average case of O(1) and a worst case of O(n).

The common complexity classes, in increasing growth order, are:

Class Time example Auxiliary space example
O(1) Array indexing; one CPU operation O(1)
O(log n) Binary search in a sorted array O(1) with an iterative implementation
O(n) Scanning an array O(1)
O(n log n) Merge sort O(n)
O(n²) Comparing every pair of array elements O(1)
O(2ⁿ) Enumerating all subsets O(n) recursion stack
O(n!) Enumerating all permutations O(n) recursion stack

How Caching Changes Complexity

Let:

  • N be the number of requests.

  • L be the cost of checking the cache layers.

  • M be the number of cache misses.

  • B be the average backend work required per miss.

The aggregate time is:

O(N × L + M × B)

If each miss performs an O(k) backend operation and the hit rate is h, the expected number of misses is approximately N × (1 - h), giving:

O(N × L + N × (1 - h) × k)

For a typical hash-based cache with O(1) expected lookup:

  • Best case: Every request hits, giving O(N).

  • Average case: Misses pay the backend cost, giving O(N(1 - h)k + N).

  • Worst case: Every request misses, giving O(Nk). Hash-table lookup itself can degrade to O(n) with n entries in a collision-heavy case.

A cache does not turn an O(k) backend operation into O(1) on a miss. It changes how often that operation occurs. Distributed caches and CDNs also add network and serialization costs, which affect latency and throughput even when they do not change the formal Big-O class.

Deriving System Complexity

When combining operations:

  • Sequential steps: Add their costs, such as O(n) + O(log n) = O(n).

  • Nested loops: Multiply their iteration counts, such as O(n) × O(n) = O(n²).

  • Conditional branches: Use the worst applicable branch unless behavior is averaged over a known distribution.

  • Recursion: Derive a recurrence and solve it directly or use the Master Theorem when its assumptions apply.

  • Drop constants and lower-order terms: 3n² + 2n + 5 becomes O(n²).

With multiple caching layers, a request may traverse several lookups until one hits. The first successful layer avoids the slower layers, so average cost depends on each layer’s hit rate, access latency, and miss rate.

Amortized and Space Analysis

A dynamic-array append is O(1) amortized because occasional O(n) resizing costs are spread across many O(1) appends. One individual append can still take O(n) in the worst case.

Cache space is proportional to the number and size of retained entries. For u cached items of average size s, this is O(u × s). Without eviction, u may grow to O(N); a cache with fixed capacity C uses O(C × s). Local caches consume process memory, while distributed caches consume server memory and network capacity, plus persistent storage only when persistence is configured.

These analyses exclude the original input unless stated otherwise. Auxiliary structures and recursion stacks are included in space complexity.

Worked Example

  1. The first request for a user arrives with an empty cache. The lookup misses, so the request performs an O(1) expected cache lookup followed by an O(k) backend scan.

  2. The backend returns the result, and the cache stores one new entry.

  3. A repeated request finds that entry. It returns in O(1) expected time without repeating the O(k) backend scan.

  4. The cache stores O(u) entries for u distinct cached users. The original backing records are not included in the auxiliary-space calculation.

Interview Tips

  • Distinguish average-case improvement from a change in an algorithm’s asymptotic bound.

  • Mention lookup, serialization, eviction, and network overhead rather than assuming every hit has constant cost.

  • Discuss invalidation and eviction: stale data and capacity limits affect correctness and hit rates, even when they do not alter Big-O.

  • State whether input storage and the recursion stack are included in space calculations.

  • Follow-ups commonly ask about cache stampedes, thundering herds, TTLs, eviction policies, and how hit rate affects total cost.

20

How do you calculate Big-O complexity for a recursive algorithm?

Big-O notation provides an asymptotic upper bound on how an algorithm’s resource usage grows with input size. For recursive algorithms, calculate the runtime by deriving and solving a recurrence relation, then include the recursion stack when determining space complexity.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Big-O, Big-Omega, and Big-Theta

  • Big-O: An asymptotic upper bound. For example, binary search runs in O(log n).

  • Big-Omega: An asymptotic lower bound. For example, binary search performs at least Ω(log n) comparisons in its worst case.

  • Big-Theta: A tight bound where upper and lower bounds match. For example, binary search runs in Θ(log n) in its worst case.

Best, average, and worst cases are separate from these bounds:

  • Best case: The most favorable input, such as finding a target immediately in binary search: O(1).

  • Average case: The expected complexity under a stated input distribution, such as a uniformly distributed binary-search target: O(log n).

  • Worst case: The least favorable valid input, such as a binary-search target requiring repeated halving: Θ(log n).

Common Complexity Classes

Class Example
O(1) Reading a fixed number of array elements
O(log n) Binary search on a sorted list
O(n) Linear scan or recursive factorial
O(n log n) Merge sort
O(n²) Bubble sort or checking every pair
O(2ⁿ) Recursively branching over every decision
O(n!) Generating every permutation

Deriving a Recursive Bound

  1. Identify the base case: This stops the recursion.

  2. Count recursive calls: If each call creates a recursive calls on an input of size n / b, use T(n) = aT(n / b) + f(n).

  3. Count nonrecursive work: f(n) represents operations performed at each call.

  4. Solve the recurrence: Use a recursion tree, substitution, or the Master Theorem.

  5. Simplify the result: Remove constants and lower-order terms.

Typical recurrence examples:

  • Factorial: T(n) = T(n - 1) + O(1) → O(n).

  • Binary search worst case: T(n) = T(n / 2) + O(1) → O(log n).

  • Merge sort: T(n) = 2T(n / 2) + O(n) → O(n log n).

  • Naive Fibonacci: T(n) = T(n - 1) + T(n - 2) + O(1) → O(2ⁿ).

For T(n) = aT(n / b) + f(n), let d = log_b(a). The Master Theorem commonly gives:

  • If f(n) = O(n^(d - ε)), then T(n) = O(n^d).

  • If f(n) = Θ(n^d), then T(n) = O(n^d log n).

  • If f(n) = Ω(n^(d + ε)) and the regularity condition a f(n/b) ≤ c f(n) holds for some constant c < 1, then T(n) = O(n^d).

Here, ε > 0. If these conditions do not apply, use a recursion tree or substitution proof.

Space and Amortized Analysis

  • Auxiliary space normally excludes the input but includes the recursion stack.

  • Recursive factorial uses O(n) stack frames, or O(n) auxiliary space under the unit-cost model.

  • Recursive binary search uses O(log n) stack space in the worst case and O(1) if it finds the target before recursing.

  • Naive recursive Fibonacci uses O(n) stack space.

  • If the input is counted, add its size—for example, binary search uses O(n) total space when the input array is included.

  • Dynamic-array append: The best case is O(1), the average case over random append sequences is O(1), the worst case for one append is O(n) when resizing occurs, and the amortized cost is O(1). Geometric growth makes n appends cost O(n) overall.

Code Example

The time labels below use the standard interview model in which each arithmetic operation and stack slot costs O(1). Python’s arbitrary-precision integers have additional bit-level costs.

from bisect import bisect_left


def factorial(number: int) -> int:
    """Calculate factorial recursively for a non-negative integer."""
    if number < 0:
        raise ValueError("number must be non-negative")
    if number <= 1:
        return 1
    return number * factorial(number - 1)


factorial(4)  # 24; O(n) time and O(n) recursion-stack space


def recursive_tree_size(depth: int) -> int:
    """Count nodes in a perfect binary tree of the given depth."""
    if depth < 0:
        raise ValueError("depth must be non-negative")
    if depth == 0:
        return 1
    return 1 + 2 * recursive_tree_size(depth - 1)


recursive_tree_size(3)  # 7; O(2^depth) time and O(depth) stack space


def sorted_insertion_index(values: list[int], target: int) -> int:
    """Return the leftmost insertion index for target in a sorted list."""
    return bisect_left(values, target)


sorted_insertion_index([1, 3, 5, 7], 5)  # 2; O(log n) time, O(1) auxiliary space

For factorial(4), the calls expand as factorial(4) → factorial(3) → factorial(2) → factorial(1). There are four calls, so the operation count and stack depth are both O(n).

Relevant edge cases include empty lists, one-element inputs, duplicates, negative values, and already sorted input. The insertion function returns 0 for an empty list and uses bisect_left to find the leftmost position among duplicates; it assumes the list is sorted. Recursive graph traversals must additionally handle disconnected components and cycles.

Common Pitfalls

  • Do not use Big-O to mean average-case complexity.

  • Include work from every recursion-tree level, not just the first.

  • Include the call stack in recursive space complexity.

  • Check off-by-one conditions in base cases and array boundaries.

  • Recursive Python solutions may exceed the default recursion limit of roughly 1,000.

  • Python integers do not overflow, although arbitrary-precision arithmetic affects bit-level complexity.

  • Avoid unintentionally mutating input when the algorithm should preserve it.

  • Graph traversals need a visited set to prevent cycles.

  • Interviewers commonly ask for the recurrence, base case, best/average/worst cases, and why each bound applies.

21

How can binary search be implemented with complexity analysis?

Binary search finds a target in a sorted collection by repeatedly comparing the target with the middle element and discarding half of the remaining search range. Its time complexity is O(log n) because each comparison reduces the problem size by half.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Big-O, Big-Omega, and Big-Theta

  • Big-O: An upper-bound notation. If f(n) is the running time, f(n) ∈ O(g(n)) means f(n) grows no faster than a constant multiple of g(n) for sufficiently large n.

  • Big-Omega: A lower-bound notation. f(n) ∈ Ω(g(n)) means f(n) grows at least as fast as a constant multiple of g(n).

  • Big-Theta: A tight bound. f(n) ∈ Θ(g(n)) means both an O(g(n)) upper bound and an Ω(g(n)) lower bound apply.

  • Case analysis is separate from these notations. Average, best, and worst cases describe how behavior changes for different inputs; they do not change what Big-O means.

For binary search, the worst and average running times are Θ(log n), so O(log n) is also a correct upper bound.

Common Complexity Classes

Class Typical example
O(1) values[0] # O(1)
O(log n) binary_search(values, target) # O(log n)
O(n) sum(values) # O(n)
O(n log n) sorted(values) # O(n log n) average/worst
O(n^2) Comparing every pair of elements
O(2^n) A recursion that explores every subset
O(n!) A recursion that explores every permutation

These classes are ordered by asymptotic growth: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!).

Deriving Complexity

  • Drop constants and lower-order terms: 3n + 20 becomes O(n).

  • Sequential steps add: scanning an array and then another costs O(n) + O(n) = O(n).

  • Nested loops multiply: two nested loops over n elements usually cost O(n²).

  • Recursion uses a recurrence: for example, T(n) = 2T(n/2) + Θ(n) gives Θ(n log n) by the Master Theorem.

  • Amortized analysis: appending to a dynamic array costs O(1) amortized, even though an occasional capacity resize costs O(n).

Auxiliary space includes temporary variables and the recursion stack. The input collection is normally excluded from auxiliary space, so a list of n integers occupies O(n) input space but does not automatically count toward an algorithm’s auxiliary-space bound.

Binary Search Analysis

Binary search requires the collection to be sorted in the same order used by the comparisons.

  1. Compare the target with the middle element.

  2. If they match, return the middle index.

  3. If the target is larger, search only the right half.

  4. If the target is smaller, search only the left half.

  5. Return -1 when the search range becomes empty.

The complexities are:

  • Best time: O(1) — the target matches the first middle element examined.

  • Average time: Θ(log n) — over possible target positions, each comparison eliminates roughly half the remaining elements.

  • Worst time: Θ(log n) — the target is absent or near the end, so the search continues until only one candidate remains.

  • Auxiliary space: O(1) — the iterative implementation uses only a few variables. The input list’s O(n) space is not counted as auxiliary space.

  • Recursive space: O(log n) — a recursive version would add an O(log n) call stack.

For example, searching for 7 in [1, 3, 5, 7, 9, 11] examines 5, then 9, then 7, requiring three comparisons.

Code Example

from collections.abc import Sequence


def binary_search(values: Sequence[int], target: int) -> int:
    """Return an index of target in sorted values, or -1 if it is absent."""
    left, right = 0, len(values) - 1

    while left <= right:
        middle = left + (right - left) // 2

        if values[middle] == target:
            return middle
        elif values[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1


print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3

The function handles empty input, one-element input, negative numbers, and already sorted input. With duplicates, it returns one matching index rather than necessarily the first or last occurrence.

Common Pitfalls

  • Unsorted input: Binary search gives incorrect results unless the collection is sorted.

  • Off-by-one errors: Use inclusive left and right bounds, or consistently use a half-open interval.

  • Overflow in other languages: Prefer left + (right - left) // 2 over (left + right) // 2.

  • Duplicate ambiguity: Specify whether the API must return the first match, last match, or any match.

  • Unexpected mutation: The implementation above does not modify the input.

  • Common follow-up: Interviewers may ask for a lower_bound variant that returns the insertion position for duplicates.

22

How can nested loop algorithms be optimized for better Big-O complexity?

Big-O notation describes an asymptotic upper bound on an algorithm’s resource usage as input size grows. Optimizing a nested loop requires identifying redundant work and replacing it with a data structure, sorting strategy, or recurrence that reduces the number of operations.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Big-O, Big-Omega, and Big-Theta

  • Big-O: An upper-bound notation. If f(n) = O(g(n)), constants exist such that f(n) <= c × g(n) for sufficiently large n.

  • Big-Omega: A lower-bound notation, stating that an algorithm requires at least a certain amount of work.

  • Big-Theta: A tight bound that matches both an upper and lower bound.

  • Big-O does not mean “average case.” Best, average, and worst cases describe different input scenarios; they are separate from the O/Omega/Theta notation system.

To derive complexity:

  • Drop constants and lower-order terms: 3n² + 2n + 1 becomes O(n²).

  • Add sequential steps: O(n) + O(n) becomes O(n).

  • Multiply nested steps: O(n) × O(n) becomes O(n²).

  • Analyze recursion using a recurrence such as T(n) = 2T(n/2) + O(n).

  • Use the Master Theorem when its conditions apply.

Common Complexity Classes

Class Typical example Best Average Worst Auxiliary space
O(1) Array indexing O(1) O(1) O(1) O(1)
O(log n) Binary search O(log n) O(log n) O(log n) O(1)
O(n) Linear scan O(n) O(n) O(n) O(1)
O(n log n) Python sorted() O(n) O(n log n) O(n log n) O(n)
O(n²) Nested scan O(n²) O(n²) O(n²) O(1)
O(2^n) Binary decision tree O(2^n) O(2^n) O(2^n) O(n) stack
O(n!) Exhaustive permutation tree O(n!) O(n!) O(n!) O(n) stack

Optimizing Nested Loops

For example, finding whether two distinct array positions sum to a target can be implemented with nested loops. Every pair is examined, producing O(n²) worst-case time.

Approach Best time Average time Worst time Auxiliary space When to use
Nested pair scan O(1) O(n²) O(n²) O(1) Very small inputs or simple cases
Hash set O(1) O(n) O(n²) O(n) Typical fast solution
Sort and two pointers O(n) O(n log n) O(n log n) O(n) Predictable runtime is important

The hash-set solution stores previously seen values. Instead of rescanning the array for each complement, it performs one expected O(1) lookup per element. Python hashing provides expected O(1) operations, but adversarial collisions can degrade the worst case to O(n²).

There is no universal nested-loop optimization. The correct technique depends on the problem’s semantics, whether the input may be modified, and whether average or worst-case performance matters.

Space and Amortized Analysis

  • Auxiliary space excludes the input and counts temporary data plus the recursion stack.

  • Total space includes the input; the hash-set solution uses O(n) auxiliary and O(n) total space.

  • Recursive examples use O(n) call-stack space.

  • Dynamic-array append has amortized O(1) time because occasional resizing is spread across many operations, although one append can take O(n) worst-case time.

  • Union-find with union by rank and path compression has amortized O(α(n)) time per operation, where α grows extremely slowly.

Code Example

from bisect import bisect_left


def access_first(values: list[int]) -> int:
    """Return the first value; O(1) time and O(1) auxiliary space."""
    if not values:
        raise ValueError("values must not be empty")
    return values[0]


print(access_first([7]))  # 7


def binary_search(values: list[int], target: int) -> int:
    """Search sorted values; O(log n) time and O(1) auxiliary space."""
    if not values:
        return -1
    index = bisect_left(values, target)
    return index if index < len(values) and values[index] == target else -1


print(binary_search([1, 3, 5, 7], 5))  # 2


def linear_search(values: list[int], target: int) -> int:
    """Scan values; O(n) time and O(1) auxiliary space."""
    for index, value in enumerate(values):
        if value == target:
            return index
    return -1


print(linear_search([4, -1, 6], 6))  # 2


def sorted_copy(values: list[int]) -> list[int]:
    """Return a sorted copy; O(n log n) time and O(n) auxiliary space."""
    return sorted(values)


print(sorted_copy([3, 1, 2]))  # [1, 2, 3]


def nested_pair_sum(values: list[int], target: int) -> bool:
    """Check every pair; O(n^2) time and O(1) auxiliary space."""
    for left in range(len(values)):
        for right in range(left + 1, len(values)):
            if values[left] + values[right] == target:
                return True
    return False


print(nested_pair_sum([1, 2, 4], 6))  # True


def binary_tree_leaves(depth: int) -> int:
    """Count leaves in a full binary tree of given depth; O(2^n) time and O(n) stack space."""
    if depth < 0:
        raise ValueError("depth must be non-negative")

    def visit(level: int) -> int:
        if level == depth:
            return 1
        return visit(level + 1) + visit(level + 1)

    return visit(0)


print(binary_tree_leaves(3))  # 8


def permutation_leaf_count(size: int) -> int:
    """Count permutation leaves; O(n!) time and O(n) auxiliary space."""
    if size < 0:
        raise ValueError("size must be non-negative")
    values = list(range(size))

    def visit(position: int) -> int:
        if position == size:
            return 1
        leaves = 0
        for index in range(position, size):
            values[position], values[index] = values[index], values[position]
            leaves += visit(position + 1)
            values[position], values[index] = values[index], values[position]
        return leaves

    return visit(0)


print(permutation_leaf_count(3))  # 6


def has_pair_sum(values: list[int], target: int) -> bool:
    """Return whether two distinct positions sum to target."""
    seen: set[int] = set()
    for value in values:
        # Average O(n) time, O(n) worst case with collisions, O(n) space.
        if target - value in seen:
            return True
        seen.add(value)
    return False


print(has_pair_sum([1, 2, 4], 6))  # True

Interview Tips

  • Distinguish average-case hashing from guaranteed O(n log n) sorting.

  • State whether input storage is included in the space calculation.

  • Count recursive calls as stack space, and mention Python’s approximately 1,000-frame recursion limit.

  • The hash solution handles empty and one-element inputs, duplicates, and negative values without mutating the input.

  • Watch for off-by-one errors when two positions must be distinct: use left + 1, not left.

23

How do you design a divide-and-conquer merge sort and analyze its complexity?

A divide-and-conquer merge sort recursively divides the input into smaller subarrays, sorts each half, and merges the sorted halves. Its tight time complexity is Θ(n log n) in the best, average, and worst cases, while its auxiliary space complexity is O(n), including the recursion stack.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Divide and Conquer Works

Merge sort applies three steps:

  1. Divide: Split the array into two approximately equal halves.

  2. Conquer: Recursively sort both halves until each contains at most one element.

  3. Combine: Merge the two sorted halves by repeatedly selecting the smaller front element.

For [5, -1, 3, 3, 0]:

Step Values
Initial split [5, -1, 3] and [3, 0]
Split left half [5, -1] and [3]
Sort recursively [-1, 5] and [3]
Sort right half [3] and [0]
Merge halves [-1, 3, 5] and [0, 3]
Final merge [-1, 0, 3, 3, 5]

Complexity Analysis

The recurrence for merge sort is:

T(n) = 2T(n / 2) + Θ(n)

  • Recursive work: Two subproblems of size n / 2.

  • Merge work: Each element is copied once per level, so one merge costs Θ(n).

  • Result: By the Master Theorem, T(n) = Θ(n log n).

Case Time
Best Θ(n log n)
Average Θ(n log n)
Worst Θ(n log n)
  • Auxiliary space: O(n) for merged lists.

  • Recursion stack: O(log n) because each recursive call halves the input.

  • Input storage: Conventionally excluded from auxiliary-space analysis; including the input or output still gives O(n) total storage.

  • Mutability: The implementation below does not mutate the caller’s list.

Compared with quadratic comparison sorting:

Approach Best Average Worst Auxiliary Space When to Use
Selection sort Θ(n²) Θ(n²) Θ(n²) O(1) Very small inputs or minimal extra memory
Merge sort Θ(n log n) Θ(n log n) Θ(n log n) O(n) Stable sorting and large comparison-sorted inputs

Big-O, Big-Omega, and Big-Theta

  • Big-O: An upper bound on growth, such as O(n log n).

  • Big-Omega: A lower bound; for example, comparison-based sorting has a worst-case Ω(n log n) lower bound.

  • Big-Theta: A matching upper and lower bound, meaning the tight complexity is Θ(n log n).

Best, average, and worst case describe the input conditions under which a bound applies. They are separate from the choice of O, Ω, or Θ.

Common Class Example
O(1) Accessing an array element by index
O(log n) Binary search in a sorted list
O(n) Scanning every element
O(n log n) Merge sort
O(n²) Comparing every pair of elements
O(2^n) Enumerating all subsets
O(n!) Enumerating all permutations

To derive complexity, drop constants and lower-order terms, add costs of sequential steps, multiply costs of nested loops, and solve a recurrence directly or with the Master Theorem.

Amortized analysis is separate from best/average/worst analysis. Appending to a dynamic array takes O(1) amortized time because occasional O(n) resizes are spread across many appends; n appends therefore cost O(n) in total.

Code Example

from typing import TypeVar

T = TypeVar("T")


def merge_sort(values: list[T]) -> list[T]:
    """Return a sorted copy of values using divide-and-conquer merge sort."""
    # Time: Θ(n log n); auxiliary space: Θ(n), including Θ(log n) stack space.
    if len(values) <= 1:
        return values.copy()

    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])

    merged: list[T] = []
    left_index = 0
    right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    return merged


if __name__ == "__main__":
    print(merge_sort([5, -1, 3, 3, 0]))  # [-1, 0, 3, 3, 5]

The implementation handles empty input, one element, duplicates, negative numbers, and already sorted input. It uses <= during merging, making the sort stable.

Common Pitfalls

  • Using O as if it always meant average-case complexity.

  • Forgetting the O(n) merge cost or the O(log n) recursion stack.

  • Assuming all merge-sort implementations use only O(log n) space.

  • Introducing off-by-one errors when handling leftover elements after a merge.

  • Accidentally mutating the input when an in-place variant was not requested.

  • A visited set is unnecessary because merge sort processes each subarray only once.

  • Calculating n * log₂(n) in a fixed-width integer can overflow in languages such as C++ or Java.

Interview Tips

Common follow-up questions ask whether merge sort is stable, how an in-place version differs, why the comparison-sorting lower bound is Ω(n log n), and how merge sort compares with quicksort and heapsort. Emphasize predictable Θ(n log n) runtime, stability, and the tradeoff of O(n) auxiliary space.

24

How do you implement dynamic programming for minimum coin change?

Dynamic programming solves minimum coin change by storing the optimal result for every amount up to the target. For target amount amount and coin denominations coins, the bottom-up solution runs in O(amount × len(coins)) time and O(amount) auxiliary space.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Dynamic Programming Approach

Let dp[x] represent the minimum number of coins needed to make amount x.

The recurrence is:

dp[x] = min(dp[x], 1 + dp[x - coin]) for every coin where coin <= x, treating an unreachable predecessor as infinity.

The base case is dp[0] = 0. If no combination can produce an amount, its value remains unreachable.

For example, with coins = [1, 3, 4] and amount = 6:

Amount Optimal combination dp value
0 No coins 0
1 1 1
2 1 + 1 2
3 3 1
4 4 1
5 4 + 1 2
6 3 + 3 2

Complexity Bounds and Common Classes

  • Big-O describes an asymptotic upper bound.

  • Big-Omega describes an asymptotic lower bound.

  • Big-Theta describes a tight bound that is both an upper and lower bound.

  • Best, average, and worst cases describe different input conditions; they are separate from Big-O, Big-Omega, and Big-Theta.

Common complexity classes, in increasing order:

Class Example
O(1) Indexing one element of a Python list
O(log n) Binary search in a sorted list
O(n) Scanning every list element
O(n log n) Merge sort
O(n²) Comparing every pair of elements
O(2ⁿ) The 2ⁿ possible subsets of n distinct items
O(n!) The n! possible orderings of n distinct items

To derive complexity:

  • Drop constants and lower-order terms: 3n + 5 becomes O(n).

  • Add sequential steps: O(n) + O(log n) becomes O(n).

  • Multiply nested operations: n iterations containing n work become O(n²).

  • Analyze recursion with a recurrence or the Master Theorem. For example, T(n) = 2T(n/2) + O(n) gives Θ(n log n).

Time and Space Analysis

Let k = len(coins) and A = amount.

Case Time Auxiliary space Reason
Best O(kA) O(A) Every amount checks every denomination, regardless of ordering
Average O(kA) O(A) The same nested loops execute for each target
Worst O(kA) O(A) Every denomination is checked for every amount

The auxiliary space is O(A) for the dp array; the input is not counted. Including the input, total space is O(k + A). This iterative implementation has no recursion stack. A recursive memoized version would additionally use up to O(A) call-stack space.

Approach Time Space When to use
Exhaustive recursion O(kᴬ) O(A) Only for very small inputs
Bottom-up dynamic programming O(kA) O(A) General minimum coin change
Greedy selection after sorting O(k log k) O(k) Only for denomination systems known to admit an optimal greedy choice

The greedy row includes sorting; Python 3.12 sorting can use O(k) auxiliary space, while the greedy scan itself uses O(1) space.

This DP is pseudo-polynomial because its runtime depends on the numeric target, not merely the number of bits needed to represent it.

Code Example

def min_coin_change(coins: list[int], amount: int) -> int:
    """Return the minimum coins needed, or -1 if the amount is unreachable."""
    if amount < 0:
        raise ValueError("amount must be non-negative")
    if any(coin <= 0 for coin in coins):
        raise ValueError("coin denominations must be positive")

    if amount == 0:
        return 0
    if not coins:
        return -1

    # Any valid solution uses at most `amount` positive-value coins.
    unreachable = amount + 1
    dp = [unreachable] * (amount + 1)
    dp[0] = 0

    # Time: O(k * amount); auxiliary space: O(amount), excluding the input.
    for current_amount in range(1, amount + 1):
        for coin in coins:
            if coin <= current_amount:
                dp[current_amount] = min(
                    dp[current_amount],
                    dp[current_amount - coin] + 1,
                )

    return -1 if dp[amount] == unreachable else dp[amount]


print(min_coin_change([1, 3, 4], 6))  # 2 (coins 3 + 3)

Best Practices and Edge Cases

  • Empty coin list: returns 0 for amount 0 and -1 for a positive amount.

  • Zero amount: requires zero coins.

  • Duplicates: do not affect the minimum count, although they may increase runtime.

  • Negative denominations: rejected with ValueError.

  • Unsorted coins: work unchanged because the algorithm does not rely on ordering.

  • Unreachable amounts: return -1.

  • Very large targets: consider a different algorithm because the array-based DP consumes O(A) memory.

Common Pitfalls

  • Making off-by-one errors when initializing or updating dp.

  • Forgetting to initialize dp[0] = 0.

  • Using a sentinel that could also represent a valid solution; amount + 1 is safe for positive integer coins.

  • Allowing amount + 1 to overflow in a fixed-width language; use a sufficiently wide type or another unreachable marker.

  • Assuming greedy selection always works: for [1, 3, 4] and amount 6, greedy selects 4 + 1 + 1, while the optimum is 3 + 3.

  • A common follow-up asks how to reconstruct the actual coin combination, usually by storing the chosen coin alongside each DP value.

25

How do you refactor a recursive algorithm using memoization and analyze complexity?

Memoization caches previously computed recursive states so that overlapping work is performed only once. It can reduce exponential time to linear time when subproblems repeat, at the cost of cache storage while usually retaining the recursion stack.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Big-O, Big-Omega, and Big-Theta

  • Big-O: An upper bound. If f(n) = O(g(n)), constants c and n₀ exist such that f(n) ≤ c × g(n) for every n ≥ n₀.

  • Big-Omega: A lower bound. If f(n) = Ω(g(n)), then f(n) eventually grows at least as quickly as g(n).

  • Big-Theta: A tight bound. If f(n) = Θ(g(n)), the function has matching upper and lower bounds.

  • Best, average, and worst case describe performance under different input or execution conditions; they are separate from Big-O, Big-Omega, and Big-Theta.

To derive complexity, drop constants and lower-order terms, add sequential costs, multiply nested-loop costs, and analyze recursion with a recurrence or the Master Theorem.

An amortized bound describes a sequence of operations. Dynamic-array append is amortized O(1): one append can take O(n) during reallocation, but n appends perform O(n) total reallocation work. Its backing storage is O(n).

The bounds below use the standard unit-cost arithmetic model, where each arithmetic operation and stored integer count as O(1); input storage is excluded from auxiliary space.

Common Complexity Classes

Class Example Time Auxiliary space and reason
O(1) Accessing a list element by index O(1): direct index calculation O(1): no additional container
O(log n) Binary search on a sorted list O(log n): the search range halves O(1): only search bounds are stored
O(n) Summing every list element O(n): each element is visited once O(1): only an accumulator is needed
O(n log n) Merge sort O(n log n): O(log n) levels with linear merging O(n): a merge buffer is required
O(n²) Optimized bubble sort Best O(n); average/worst O(n²) O(1): elements are swapped in place
O(2ⁿ) Generating every subset O(2ⁿ): two choices per element O(n): recursion path and current subset
O(n!) Generating every permutation O(n!): all orderings are produced O(n): current permutation and recursion stack

Refactoring and Complexity Change

  1. Identify recursive states containing overlapping subproblems.

  2. Create a cache key containing every value that affects the result.

  3. Return the cached result when the key exists.

  4. Handle base cases before making recursive calls.

  5. Compute, cache, and return the result for each new state.

For naive recursive Fibonacci, T(n) = T(n - 1) + T(n - 2) + O(1), giving O(φⁿ) time in the best, average, and worst cases. Its O(n) auxiliary space comes from the recursion stack.

Approach Time Space When to use
Naive recursion O(φⁿ) in all cases O(n) stack Small inputs or baseline comparison
Memoized recursion Best/average O(n); generic hash-table worst case O(n²) O(n) cache plus O(n) stack Recursive problems with overlapping states

Memoization creates only n + 1 distinct states, each requiring expected O(1) dictionary work. Under pathological hash collisions, an O(n) lookup can increase the generic worst-case bound to O(n²). Cache and stack storage total O(n) in the unit-cost model.

Step-by-step for fibonacci(5):

  1. solve(5) is uncached and requests solve(4).

  2. solve(4) requests solve(3).

  3. solve(3) requests solve(2), which computes and caches 0, 1, and 2; solve(3) then caches 2.

  4. solve(4) reuses cached solve(2) and caches 3.

  5. solve(5) reuses cached solve(3) and returns 5.

Code Example

def fibonacci(n: int) -> int:
    """Return the nth Fibonacci number using memoized recursion."""
    if n < 0:
        raise ValueError("n must be non-negative")

    memo: dict[int, int] = {}

    def solve(index: int) -> int:
        if index in memo:
            return memo[index]

        if index <= 1:
            memo[index] = index
            return index

        memo[index] = solve(index - 1) + solve(index - 2)
        return memo[index]

    return solve(n)


# Time: O(n) average; O(n^2) worst case with pathological hash collisions.
# Space: O(n), including cache and recursion stack; input excluded.
print(fibonacci(5))  # 5

Common Pitfalls

  • Incorrect cache keys: Include every input that affects the result.

  • Unnecessary caching: Memoization is ineffective when states never repeat.

  • Recursion depth: Python’s default limit is approximately 1000; use iterative dynamic programming or carefully raise the limit for larger inputs.

  • Space accounting: Include both the cache and recursion stack and state whether input storage is excluded.

  • Complexity terminology: Do not use “Big-O” as a synonym for average case.

  • Edge cases: Test n = 0, n = 1, and negative inputs. Duplicates, sortedness, disconnected graphs, and cycles are not applicable to Fibonacci.

26

How do you develop efficient multithreaded algorithms and analyze their complexity?

Efficient multithreaded algorithms divide work among workers while preserving correctness and coordinating the results. Big-O complexity measures asymptotic work, but it does not guarantee faster execution; actual speed depends on hardware, contention, task overhead, and workload characteristics.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Big-O, Big-Omega, and Big-Theta

  • Big-O: An upper-bound notation. If f(n) = O(g(n)), then f(n) ≤ c·g(n) for some constant c and sufficiently large n.

  • Big-Omega: A lower-bound notation. If f(n) = Ω(g(n)), then f(n) ≥ c·g(n) eventually.

  • Big-Theta: A tight-bound notation. If f(n) = Θ(g(n)), both bounds hold, so the growth rate is precisely characterized.

  • Best, average, and worst case describe how behavior changes with different inputs or conditions. They are separate from O, Ω, and Θ. Saying “O(n) average” is imprecise; “average-case time is Θ(n)” is clearer.

Common Complexity Classes

Class Example
O(1) Accessing values[index] in an array
O(log n) Binary search in a sorted list
O(n) Scanning every array element
O(n log n) Merge sort
O(n²) Comparing every pair of elements
O(2ⁿ) Enumerating all subsets of an n-element set
O(n!) Enumerating all permutations

Designing Multithreaded Algorithms

  1. Partition the work into independent tasks that can execute concurrently.

  2. Minimize synchronization by giving workers private, preferably immutable, data.

  3. Combine results deterministically, often by merging, reducing, or collecting indexed results.

  4. Bound the worker pool to avoid excessive context switching and memory use.

  5. Evaluate both work and elapsed time:

  6. Total work is the sum of all workers’ operations.

  7. Parallel span is the length of the critical path.

  8. Wall-clock time also includes scheduling and synchronization overhead.

For divide-and-conquer algorithms, derive complexity from a recurrence such as T(n) = 2T(n/2) + O(n). Sequential steps add their complexities, nested loops multiply them, and constants and lower-order terms are dropped when finding the dominant term.

Amdahl’s Law estimates ideal speedup as 1 / ((1 - s) + s/p), where s is the parallelizable fraction and p is the worker count. It shows why limited parallelism prevents linear speedup.

Code Example

The following parallel merge sort merges sorted runs concurrently in rounds. It does not mutate the input.

from concurrent.futures import ThreadPoolExecutor


def _merge_sorted(left: list[int], right: list[int]) -> list[int]:
    """Merge two sorted lists in O(n) time and O(n) space for the result."""
    merged: list[int] = []
    left_index = right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    return merged


def parallel_merge_sort(
    values: list[int], max_workers: int = 4
) -> list[int]:
    """Sort integers concurrently without modifying the input."""
    if max_workers < 1:
        raise ValueError("max_workers must be at least 1")
    if not values:
        return []
    if len(values) == 1:
        return values.copy()

    runs: list[list[int]] = [[value] for value in values]

    while len(runs) > 1:
        workers = min(max_workers, max(1, len(runs) // 2))
        futures = []

        with ThreadPoolExecutor(max_workers=workers) as executor:
            for index in range(0, len(runs) - 1, 2):
                futures.append(
                    executor.submit(
                        _merge_sorted,
                        runs[index],
                        runs[index + 1],
                    )
                )

        merged_runs: list[list[int]] = []
        for future in futures:
            merged_runs.append(future.result())

        # Carry an unmatched run into the next round.
        if len(runs) % 2 == 1:
            merged_runs.append(runs[-1])

        runs = merged_runs

    # Time: O(n log n) total work; space: O(n) auxiliary.
    return runs[0]


print(parallel_merge_sort([5, 3, 8, 1], max_workers=4))
# Expected output: [1, 3, 5, 8]

The example progresses as follows:

Round Sorted runs
Start [5], [3], [8], [1]
1 [3, 5], [1, 8]
2 [1, 3, 5, 8]

Complexity Analysis

  • Total work/time: Best, average, and worst-case total work are all O(n log n) because each of O(log n) rounds merges O(n) elements.

  • Theoretical parallel elapsed time: Under true parallel execution and ideal scheduling, it is O(n log n / p + n) for p workers because total work is O(n log n) and span is O(n). In CPython 3.12, the GIL serializes CPU-bound Python bytecode, so this thread implementation normally receives no CPU speedup.

  • Auxiliary space: O(n + p), excluding the input, because intermediate runs, futures, and results use O(n) space while concurrent worker stacks use O(p). Since p = O(n), this is O(n).

  • Total space including input: O(n + p) because the input itself occupies O(n) space.

  • Recursion stack: This implementation is iterative, so each worker uses O(1) call-stack space; aggregate worker stacks use O(p).

The code handles empty input, one element, duplicates, negative numbers, already sorted input, and an odd number of runs.

Dynamic-array append is another useful distinction: it is O(1) amortized, although one individual append can take O(n) when resizing. Its storage is O(n) extra capacity, excluding the stored input.

Common Pitfalls

  • Do not interpret Big-O as “average case.”

  • In standard CPython 3.12, the GIL prevents CPU-bound Python bytecode from running truly concurrently. Threads are most effective for I/O-bound work; use ProcessPoolExecutor for CPU-bound parallelism.

  • Avoid sharing mutable state without proper synchronization; use locks sparingly and consistently.

  • Account for task creation, merging, and communication overhead rather than assuming every task is faster in a thread.

  • Preserve input data when callers do not expect mutation.

  • Interviewers commonly ask about work versus elapsed time, scalability, race conditions, deadlock, Amdahl’s Law, and why a theoretical O(log n) parallel speedup does not materialize in practice.

27

How does data structure choice affect algorithm Big-O complexity?

Big-O notation describes an upper bound on an algorithm’s asymptotic resource usage. Choosing a different data structure changes the cost of the operations an algorithm performs, which can change its overall time and space complexity from constant time to logarithmic, linear, quadratic, or worse.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Asymptotic Notations and Cases

For functions describing resource usage:

  • Big-O: an asymptotic upper bound; f(n) = O(g(n)) means f(n) eventually grows no faster than a constant multiple of g(n).

  • Big-Omega: an asymptotic lower bound; f(n) = Ω(g(n)) means f(n) eventually grows at least as fast as a constant multiple of g(n).

  • Big-Theta: a tight bound; f(n) = Θ(g(n)) means both bounds hold.

Best, average, and worst case are separate from these notations. For example, hash-table lookup is O(1) average time but O(n) worst-case time; the average case has an O(1) upper bound, while the worst case has an O(n) upper bound.

Common Complexity Classes

Class Tight growth Typical example Auxiliary space
O(1) Θ(1) Read the first list element O(1)
O(log n) Θ(log n) Binary-search a sorted list O(1)
O(n) Θ(n) Scan every list element O(1)
O(n log n) Θ(n log n) Comparison sort in the worst case O(n)
O(n²) Θ(n²) Examine every ordered pair O(1)
O(2ⁿ) Θ(2ⁿ) Enumerate all binary masks O(1) words
O(n!) Θ(n!) Enumerate all permutations O(n)

These are conventionally named using Big-O even when the corresponding tight bound is Big-Theta.

Data-Structure Choices

The algorithm’s control flow may remain unchanged while the cost of its primitive operations changes.

Structure Important operations Time Total space
Array/list Index; search Θ(1); Θ(n) Θ(n)
Dictionary/set Key lookup Θ(1) average; Θ(n) worst Θ(n)
Balanced search tree Search, insert, delete Θ(log n) Θ(n)
Binary heap Peek; push/extract Θ(1); Θ(log n) Θ(n)
Sorted list Binary search; middle insertion Θ(log n); Θ(n) Θ(n)
Deque Add/remove at either end Θ(1) Θ(n)
Adjacency matrix Edge lookup; traversal Θ(1); Θ(V²) Θ(V²)
Adjacency list BFS/DFS Θ(V + E) Θ(V + E)

For membership in [10, 20, 30]:

  1. A linear list scan compares against 10 and then 20, taking Θ(n) time.

  2. Building a set hashes each element, taking Θ(n) expected total time.

  3. Looking up 20 then examines its bucket, taking Θ(1) expected time and Θ(n) worst time.

  4. The set requires Θ(n) total space, while the list scan requires only Θ(1) auxiliary space.

Deriving and Analyzing Complexity

  • Sequential steps: add their costs, such as O(n) + O(log n) = O(n).

  • Nested loops: multiply costs, such as O(n) × O(n) = O(n²).

  • Drop constants and lower-order terms: 3n² + 2n + 5 becomes O(n²).

  • Recursion: derive a recurrence such as T(n) = 2T(n/2) + O(n). The Master Theorem can identify its asymptotic bound.

  • Amortized analysis: dynamic-array append is O(1) amortized. One append can take O(n) during resizing, but geometric capacity growth makes n appends take O(n) total.

  • Space: include output, auxiliary storage, and the recursion stack. Unless stated otherwise, code examples exclude the input and count returned collections separately.

Common Pitfalls

  • Do not use “Big-O” to mean average case.

  • Include the cost of inserting or deleting, not only searching.

  • Remember that hashing can degrade to O(n) under collisions.

  • Include recursive call-stack space.

  • Do not count the input as auxiliary space unless the algorithm copies or modifies it.

  • Interviewers commonly ask for the best, average, worst, and amortized cases, plus the expected space usage.

28

How do you analyze Big-O complexity in distributed systems?

Big-O analysis of a distributed algorithm estimates how local computation, message count, transferred bytes, and coordination rounds grow as the system becomes larger. The analysis must explicitly define its parameters and distinguish algorithmic work from network-dependent wall-clock time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Asymptotic Bounds and Case Analysis

  • Big-O: an asymptotic upper bound. For example, (O(n)) time means the operation does not grow asymptotically faster than a constant multiple of (n).

  • Big-Omega: an asymptotic lower bound.

  • Big-Theta: a tight asymptotic bound, expressing both matching upper and lower bounds.

  • Best, average, and worst cases are separate from these bounds. “Average (O(n))” does not mean “Big-O means average.”

Algorithm Best time Average time Worst time Auxiliary space
Hash-table lookup (O(1)) (O(1)) expected (O(n)) (O(1))
Sequential search (O(1)) (O(n)) (O(n)) (O(1))
Quicksort (O(nlog n)) (O(nlog n)) (O(n^2)) (O(log n)) average, (O(n)) worst

The space column excludes the input and includes the recursion stack.

Common Complexity Classes

Big-O class Example Time reason Auxiliary space
(O(1)) Access an array element by index Constant number of operations (O(1))
(O(log n)) Binary search a sorted list Search interval halves each step (O(1))
(O(n)) Scan all elements Every element is examined once (O(1))
(O(nlog n)) Merge sort (O(log n)) merge levels, each processing (O(n)) elements (O(n))
(O(n^2)) Compare every pair of elements Two nested (O(n)) loops (O(1)) if streamed
(O(2^n)) Enumerate all subsets There are (2^n) subsets (O(n)) for a bitmask
(O(n!)) Enumerate all permutations There are (n!) permutations (O(n)) for the current permutation

Distributed-System Complexity

Let:

  • (n) = number of workers or nodes

  • (m) = number of messages

  • (b) = total bytes transferred

  • ® = number of communication rounds

  • © = total local computation

  • (S) = per-node storage requirement

A complete analysis normally reports several dimensions:

  • Computation: (O©), based on the algorithm performed on each node.

  • Messages: (O(m)), such as (O(n)) for tree broadcast or (O(n^2)) for all-to-all communication.

  • Bytes: (O(b)), including message size and payload overhead.

  • Rounds: (O®), because parallel workers can communicate concurrently.

  • Wall-clock time: only meaningful after modeling processor count, network latency, bandwidth, scheduling, and stragglers.

For example, with four workers:

  1. A binary-tree broadcast sends three messages and takes two rounds: (O(n)) messages and (O(log n)) rounds.

  2. All-to-all communication sends (4 times 3 = 12) directed messages: (O(n^2)) messages.

Deriving and Amortized Analysis

  • Add sequential steps.

  • Multiply nested loops.

  • For balanced parallel work, combine equal branches using their maximum rather than their sum.

  • Analyze recursion with a recurrence such as (T(n)=aT(n/b)+f(n)). For the common case (f(n)=Theta(n^k)), the Master Theorem gives (Theta(n^{log_b a})), (Theta(n^klog n)), or (Theta(n^k)), depending on the relationship between (k) and (log_b a).

Amortized analysis is also distinct from average-case analysis. Appending to a dynamic array is (O(1)) amortized because occasional (O(n)) resizes make (n) appends cost (O(n)) in total. One individual append can take (O(n)), and total array storage is (O(n)).

For distributed space, report both (O(S)) per node and (O(nS)) aggregate storage. Include recursion stacks, queues, buffers, replicated state, and state whether the original input is counted.

Code Example

from collections import deque


def tree_broadcast_messages(worker_count: int) -> int:
    """Count messages sent by a binary-tree broadcast."""
    if worker_count < 0:
        raise ValueError("worker_count cannot be negative")
    if worker_count == 0:
        return 0

    queue: deque[int] = deque([0])
    messages = 0

    while queue:
        parent = queue.popleft()
        for child in (2 * parent + 1, 2 * parent + 2):
            if child < worker_count:
                queue.append(child)
                messages += 1

    return messages


def all_to_all_messages(worker_count: int) -> int:
    """Count directed messages in all-to-all communication."""
    if worker_count < 0:
        raise ValueError("worker_count cannot be negative")

    messages = 0
    for sender in range(worker_count):
        for receiver in range(worker_count):
            if sender != receiver:
                messages += 1

    return messages


# tree_broadcast_messages(4) -> 3  # O(n) time, O(n) auxiliary space
# all_to_all_messages(4) -> 12     # O(n²) time, O(1) auxiliary space

The examples handle zero workers, one worker, and invalid negative counts. Space excludes the integer input. The tree broadcast uses a queue to avoid recursion-depth limits.

Common Pitfalls and Interview Tips

  • Do not use “Big-O” as a synonym for average case.

  • Define every parameter, especially whether (n) means workers, messages, records, or payload size.

  • Message count and wall-clock latency are different complexity measures.

  • Include recursion stacks and explicitly state whether input storage is counted.

  • Watch off-by-one errors, such as (n^2) versus (n(n-1)) for self-message exclusion.

  • Use sufficiently wide integer types in fixed-width languages; large message counts can overflow.

  • Avoid unsynchronized mutation of shared state, and use a visited set when traversing cyclic graphs.

  • Common follow-up questions ask how complexity changes with worker count, failure rates, message size, concurrency, and whether the algorithm preserves partial correctness.

29

How does Big-O complexity apply to concurrent and parallel algorithms?

Big-O describes an asymptotic upper bound on resource growth. In concurrent and parallel systems, it can characterize computational work, wall-clock time, memory usage, or synchronization overhead, but each metric must be identified explicitly.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Asymptotic Bounds

  • Big-O: An asymptotic upper bound, such as O(n log n).

  • Big-Omega: An asymptotic lower bound, such as Ω(n).

  • Big-Theta: A tight asymptotic bound, meaning the function grows at the same rate asymptotically under both bounds.

  • Best, average, and worst case describe variation across inputs or execution conditions; they are separate from O, Ω, and Θ.

  • Amortized analysis bounds the average cost of a sequence of operations, such as appending to a dynamically resizing array.

Common Complexity Classes

Space below is auxiliary space, excluding the input and returned output unless stated otherwise. Recursion-stack space is included.

Big-O class Example and time reason Auxiliary-space reason
O(1) Read the first element: best/average/worst O(1) because one element is accessed. O(1) because only a constant number of local values are used.
O(log n) Binary search: best O(1); average/worst O(log n) because each comparison roughly halves the candidate interval. O(1) because no recursive stack is needed.
O(n) Sum all elements: best/average/worst O(n) because every element is visited once. O(1) because only an accumulator is maintained.
O(n log n) Standard merge sort: best/average/worst O(n log n) because each of log n merge levels processes O(n) elements. O(n) because merge buffers are required; returned output is additional if counted.
O(n²) Enumerate unordered pairs: best/average/worst O(n²) because there are n(n−1)/2 pairs. O(1) excluding output; retaining all pairs requires O(n²) output space.
O(2ⁿ) Count nodes in a full binary tree of depth n: best/average/worst O(2ⁿ) because the tree contains exponentially many nodes. O(n) because the recursion stack reaches depth n.
O(n!) Explore all permutation paths: best/average/worst O(n!) because there are n! complete permutations. O(n) for the recursion stack, excluding materialized output.

Concurrency and Parallelism

  • Concurrency allows multiple tasks to make progress through interleaving, switching, or overlapping I/O; it does not require simultaneous execution.

  • Parallelism executes tasks simultaneously on multiple processors or hardware resources.

  • Concurrency alone does not reduce an algorithm’s asymptotic work. It can improve responsiveness or latency when tasks wait for I/O.

  • Parallelism can reduce elapsed time, but total work normally remains O(W(n)) when work is distributed rather than duplicated.

Let:

  • W(n) be the total work across all tasks.

  • S(n) be the span, meaning the longest dependency chain.

  • p be the number of workers.

  • R(n) be the result size.

With unit-cost tasks and an ideal scheduler, parallel time has a lower bound of Ω(max(W(n)/p, S(n))) and the standard work-span upper bound O(W(n)/p + S(n)). Ignoring granularity, contention, and scheduling overhead, ideal parallel time is therefore Θ(W(n)/p + S(n)).

If p is constant, parallel wall-clock time remains O(W(n)). If p = Θ(n), ideal per-worker work can become constant, but real scheduling and communication overhead may grow with p, so constant wall-clock time is not guaranteed.

Space excludes the input. A straightforward partitioned implementation using constant state per task requires O(W(n) + R(n) + p) total auxiliary space because tasks, results, workers, and queues may coexist. Per-worker task data can be O(W(n)/p), while a worker’s call stack may require up to O(S(n)); result storage need not divide evenly among workers.

Best-case parallel performance assumes ideal scheduling and no contention. Average- and worst-case bounds depend on workload distribution, task granularity, synchronization, communication, and the scheduler, so no universal bound exists without specifying those conditions.

Amdahl’s Law

For fixed total work with serial fraction f, ideal speedup is bounded by:

Sp ≤ 1 / (f + (1 − f)/p)

As p increases, speedup approaches 1/f. If f > 0, a fixed serial portion prevents unlimited scaling. This assumes negligible overhead and unchanged total work.

Common Pitfalls and Interview Tips

  • Do not use Big-O to mean “average case”; Big-O is an upper bound.

  • State the metric being analyzed: work, elapsed time, memory, or overhead.

  • Do not claim that parallelism reduces total work; it primarily targets wall-clock time.

  • Include call stacks, worker state, queues, synchronization structures, and result storage in space analysis.

  • State whether input and output are counted.

  • In standard GIL-enabled CPython 3.12, I/O-bound tasks can benefit from threads, while CPU-bound Python threads do not execute in parallel; processes or native parallel libraries are alternatives.

  • Common follow-ups include Amdahl’s Law, work-span models, scalability limits, task granularity, communication costs, cache effects, and whether p is constant or grows with n.

30

Why Big-O matters in machine learning

Big-O notation is essential in machine learning because it quantifies how algorithm runtime and memory scale with data size, model parameters, and feature dimensions, enabling engineers to choose feasible models, estimate training costs, and optimize inference latency.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Scalability and Model Selection

  • Training complexity determines whether a model can fit on available hardware. For example, exact Gaussian Process regression is O(n³) in samples, limiting it to ~10⁴ points, while stochastic gradient descent on a linear model is O(n·d) per epoch (n samples, d features).

  • Inference complexity drives production latency. A decision tree of depth k runs in O(k), while a k-NN query without indexing is O(n·d) — prohibitive for large datasets.

  • Hyperparameter search multiplies base complexity. Grid search over m configurations multiplies training cost by m; Bayesian optimization reduces evaluations but adds O(t³) overhead for t trials.

Common Complexity Classes in ML Workflows

Operation Typical Complexity Notes
Dense matrix multiply (n×d × d×p) O(n·d·p) Dominates linear layers, attention
Sparse matrix-vector multiply O(nnz) nnz = non-zero entries; key for recommender systems
k-means clustering (iterations i) O(i·n·k·d) k clusters, d dimensions
Gradient descent (epochs e, batch b) O(e·n/b · C_forward) C_forward = forward-pass cost
Transformer self-attention (seq len L) O(L²·d) Quadratic in sequence length; motivates sparse attention
Decision tree inference (depth D) O(D) Independent of training set size
k-NN query (brute force) O(n·d) Index structures (KD-tree, HNSW) reduce to O(log n) or sublinear

Training vs. Inference Trade-offs

  • Model compression (pruning, quantization, distillation) reduces inference O(·) constants or asymptotic class (e.g., dense → sparse attention).

  • Caching and precomputation shift cost from inference to offline phase. Example: precomputing embeddings for retrieval turns O(n·d) query into O(d) lookup + O(log n) ANN search.

  • Batch vs. online learning: SGD processes O(b·d) per step; full-batch GD is O(n·d) per epoch but converges in fewer iterations for convex objectives.

Deriving Complexity in ML Pipelines

  1. Identify dominant operations: matrix multiplies, convolutions, attention, sorting, nearest-neighbor search.

  2. Count dimensions: batch size B, sequence length L, hidden size H, vocabulary V.

  3. Combine sequentially (add) and nested (multiply). Example: a Transformer layer with L tokens and H hidden units:

  4. Attention: O(L²·H) (QKᵀ) + O(L²·H) (softmax) + O(L²·H) (weighted sum) = O(L²·H)

  5. Feed-forward: O(L·H²) (two linear layers)

  6. Total per layer: O(L²·H + L·H²)

  7. Account for iterations: multiply by number of layers, epochs, or optimization steps.

Space Complexity Considerations

  • Model parameters: Transformer with L layers, H hidden, V vocab → O(L·H² + V·H).

  • Activations: Storing all layer outputs for backprop is O(L·B·H) (or O(L·B·H²) for attention maps). Gradient checkpointing trades recompute (O(·) time) for O(√L·B·H) memory.

  • Data loading: Shuffling buffers, prefetch queues add O(B·d) host/device memory.

  • Optimizer states: Adam keeps two moments per parameter → 2× parameter memory.

Interview Tips

  • Distinguish training vs. inference: Interviewers often ask “What is the complexity of using this model?” not just training.

  • Name the variables: Define n, d, L, H, B, V explicitly; ambiguity loses points.

  • Mention hardware reality: Big-O hides constants; O(n²) with a tiny constant (e.g., flash attention) can beat O(n) with large overhead.

  • Know the bottlenecks: Attention O(L²), dense matmul O(n³) for cubic algorithms (exact GP, Cholesky), and sorting O(n log n) in ranking losses.

  • Follow-up readiness: Be prepared to discuss sparse attention, low-rank approximation, quantization, or distillation as complexity-reduction techniques.

  • Don’t confuse Big-O with wall time: A O(n log n) algorithm with poor memory access can be slower than O(n²) with cache-friendly layout.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 30 Big-O Notation answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects