Algorithmic Complexity & Code-Level Optimization Questions

Direct answer

Profile first to find exactly which lines or functions dominate the time, then match the fix to the ROOT CAUSE, an algorithmic problem, interpreter overhead, or genuinely parallelizable work, moving up the ladder of invasiveness only as far as the evidence justifies, never further.

The decision ladder

1. Check the algorithm first. Before touching implementation details, confirm the complexity class itself is not the real problem (an O(n^2) approach where O(n log n) or O(n) is available). This is almost always the cheapest and biggest win when it exists, and skipping straight to a rewrite or parallelization without checking it first is a common and expensive mistake.
2. Optimize within Python. If the algorithm is already sound but constant factors are high, try vectorized operations (NumPy for numeric work), built-in functions over hand-rolled loops, and removing repeated attribute lookups or redundant work inside hot loops. This stays in pure Python, so it is the lowest-maintenance-cost lever and the whole team can read and modify it.
3. Rewrite the hot loop in C, C++, or Cython. Justified once profiling shows the REMAINING cost is dominated by unavoidable per-element interpreter overhead in a loop that resists vectorization (data-dependent branching, non-numeric per-element work). This trades a compiled build step and a smaller pool of comfortable maintainers for closing most of the interpreter-overhead gap.
4. Parallelize with multiprocessing. Justified when the work is genuinely CPU-bound (not I/O-bound, where asyncio or threading is the right tool, because the GIL, the global interpreter lock, the mechanism that lets only one thread execute Python bytecode at a time, means CPU-bound work does not scale across threads) and the work decomposes into independent chunks with low cross-process communication needs. Multiprocessing pays a real fixed cost, process startup and serializing (pickling) data across the process boundary, so it only wins once the per-chunk compute clearly outweighs that overhead.

Measurement approach

Use a profiler before guessing: cProfile for function-level timing, a line-level profiler for pinpointing the exact hot line, or a low-overhead sampling profiler for production workloads where instrumentation overhead itself would distort the measurement. Build a repeatable benchmark with fixed, representative inputs, and re-profile after EACH change, since fixing one bottleneck routinely exposes the next one further down the ladder.

Maintenance trade-offs

Pure Python stays approachable to the entire team and needs no build pipeline. A C or Cython extension needs a compilation step and shrinks the pool of engineers who can safely modify that code path. Multiprocessing adds real coordination complexity: a bug can now be a race in how results from different processes get combined, and each worker process duplicates memory (its own interpreter and its own copy of data) unless shared memory is deliberately used, a cost that is easy to overlook when only thinking about CPU time.

Direct answer

External merge sort works in two phases that never require holding more than the RAM budget at once. First, split the data into RAM-sized chunks, sort each chunk in memory, and write it out as a sorted run. Second, merge the sorted runs with a k-way merge that only needs a small read-ahead buffer per run, never a whole run, to stream out one fully sorted file. Because neither phase ever loads more than RAM allows, the whole procedure stays I/O-bound, and its cost falls out of two numbers: how many runs get produced, and how many merge passes it takes to combine them.

General formulas

With dataset size D and usable RAM R for building one sorted run:

Run generation reads the raw input once and writes the sorted runs once, so it costs 2D of I/O. The key fact that determines how many merge PASSES are needed is that a merge only needs a small sequential-read buffer per run, not the whole run, so splitting R across num_runs input buffers plus one output buffer usually still leaves each buffer large enough for efficient sequential reads, meaning ALL runs typically merge in a single pass. A single merge pass reads every run once and writes the final output once, another 2D, so:

If the runs are too numerous for the available buffer to give each one a reasonably sized slice, the fan-in per pass is capped at some k, and the number of merge passes becomes ceil(log_k(num_runs)), each adding another 2D of I/O.

Applying it to the stated numbers, and the same method at a different scale

For 100GB of data on a machine with 4GB of RAM: num_runs = ceil(100/4) = 25. Splitting 4GB across 25 runs gives roughly 160MB per run buffer for the merge, comfortably enough for efficient sequential reads, so one merge pass suffices. Total I/O is about 4 x 100GB = 400GB. At the given 200MB/s sequential throughput, that volume alone (ignoring in-memory sort time, which is small next to I/O at this scale) works out to 400,000MB / 200MB/s = 2,000 seconds, about 33 minutes, derived purely from the disk-throughput figure stated in the problem, not measured.

The exact same method generalizes without changing the approach: for 500GB of data on a machine with 16GB of RAM, num_runs = ceil(500/16) = 32, and total I/O is again about 4 x 500GB = 2,000GB by identical reasoning. Only the two input numbers change; the formulas and the single-pass justification are the same.

Parallelizing the work

Run generation is embarrassingly parallel: each chunk's read-sort-write cycle is independent of every other chunk, so P workers can each take D/P of the data concurrently, limited in practice by how much aggregate bandwidth the storage device can actually deliver (a single disk sharing 200MB/s across P readers does not multiply total throughput by P). Parallelizing the merge into a single output stream is less direct; the standard technique is range partitioning: sample the key space up front to define P disjoint, ordered key ranges (the idea behind distributed sample-sort or Hadoop's TeraSort), route each run's rows into their range's bucket during generation, then merge each range bucket independently and in parallel, since the P sorted range outputs are already ordered relative to each other and can simply be concatenated at the end.

Trade-offs and pitfalls

Choosing a smaller merge fan-in than the buffers actually support wastes an entire extra 2D pass of I/O for no reason. Assuming the full RAM budget is usable for the sort buffer, with no headroom left for the operating system and other processes, risks thrashing in practice rather than the clean numbers above. The 200MB/s SEQUENTIAL assumption breaks down if the runs share a device with other I/O-heavy work, since interleaved access degrades toward random-access speeds, well below the number the whole estimate depends on.

Direct answer

Big-O is an upper bound on growth rate ("grows no faster than"), Big Omega ($\Omega$) is a lower bound ("grows no slower than"), and Big Theta ($\Theta$) is a tight bound: both an upper and a lower bound at once, meaning the true growth rate is pinned down up to a constant factor. In everyday interview talk people say "O(n)" to mean "it's linear," but that loose usage blurs a real distinction the formal definitions make precise.

Structured elaboration

Formal definitions, each dropping constant factors and lower-order terms by design:

$f(n) = O(g(n))$ if there exist positive constants $c, n_0$ such that $f(n) \le c \cdot g(n)$ for all $n \ge n_0$. (an upper bound: the true cost is at most this fast-growing)

$f(n) = \Omega(g(n))$ if there exist positive constants $c, n_0$ such that $f(n) \ge c \cdot g(n)$ for all $n \ge n_0$. (a lower bound: the true cost is at least this fast-growing)

$f(n) = \Theta(g(n))$ if $f(n)$ is both $O(g(n))$ and $\Omega(g(n))$: the true cost is sandwiched between $c_1 \cdot g(n)$ and $c_2 \cdot g(n)$ for large $n$.

Worked example 1, insertion sort: on a reverse-sorted array of length n, insertion sort does about $\frac{n(n-1)}{2}$ comparisons and shifts (every new element has to walk past everything already placed), so its worst case is $\Theta(n^2)$: it really is quadratic there, both bounded above and below by n^2. But on an already-sorted array, each element only needs one comparison against its neighbor before it's confirmed in place, so the best case is $\Theta(n)$. Because the best and worst cases belong to different growth classes, insertion sort AS A WHOLE ALGORITHM is correctly described only as $O(n^2)$ (an upper bound that holds for every input) and $\Omega(n)$ (a lower bound achieved by at least one input family). It is not $\Theta(n^2)$ or $\Theta(n)$ overall, only within a specified case.

Worked example 2, binary search: on a sorted array of size n, each comparison halves the remaining search space, so the number of comparisons needed to narrow the window down to nothing is about $\log_2 n$, and an UNSUCCESSFUL search always runs the halving all the way down, so unsuccessful search is $\Theta(\log n)$ on every input. Successful search is the more interesting case, and the same rule used on insertion sort has to be applied honestly here: the input family where the target happens to sit at the very first probed midpoint returns after exactly ONE comparison, at any n (executed: for n=7 the first midpoint is index 3, for n=1023 it is index 511, for n=1,000,001 it is index 500,000, and each returns in 1 comparison). So binary search AS A WHOLE ALGORITHM is $O(\log n)$ and $\Omega(1)$, and it is $\Theta(\log n)$ only within a specified case: the worst case, or unsuccessful search. The contrast with insertion sort is therefore NOT "binary search has no best-case family in a different class"; it is that binary search's best-case family is a vanishing fraction of inputs (one index out of n), whereas insertion sort's $\Theta(n)$ best case covers every already-sorted array, which is why quoting binary search as "$\Theta(\log n)$" without qualification is a common shorthand that a careful answer still has to label as the worst-case bound.

When an interviewer expects which notation: Big-O is the default ask ("what's the complexity of your solution?") because it's the guarantee you promise a caller: things will not get worse than this. Omega shows up when arguing a LOWER bound on a problem itself, not a specific algorithm: comparison-based sorting needs $\Omega(n \log n)$ comparisons in the worst case because there are $n!$ possible orderings and each comparison can only rule out roughly half of the remaining possibilities, an information-theoretic argument, not a property of any one sorting algorithm. Theta is expected when a candidate is asked for a tight characterization of an algorithm whose best and worst case coincide (merge sort is $\Theta(n \log n)$ in every case), or when the interviewer wants to test whether the candidate understands that O alone never rules out an algorithm being faster than claimed.

Constant factors and lower-order terms: none of the three notations care about them. $3n^2 + 50n + 7$ is $\Theta(n^2)$, full stop, because as n grows the $n^2$ term dominates the others. This is exactly why an asymptotically worse algorithm can still beat a better one for realistic input sizes (concretely: an algorithm costing $0.1 \cdot n \log_2 n$ actually runs faster than one costing $0.5n$ for every n below 32, and only loses once n passes that crossover, even though $n \log n$ is the asymptotically worse growth rate): the notation answers "how does cost scale as n grows without bound," not "which one is faster for n=1,000."

Worked example

For n=5: insertion sort on [1,2,3,4,5] does 4 comparisons and 0 shifts (best case, linear); on [5,4,3,2,1] it does 1+2+3+4=10 comparisons and shifts, matching $\frac{5\cdot4}{2}=10$ (worst case, quadratic). For n=1,000,000: binary search needs $\lceil \log_2 1{,}000{,}000 \rceil = 20$ comparisons in the worst case, and never more, which is the concrete sense in which the WORST case is tightly $\Theta(\log n)$. It can need far fewer: a target sitting at index 500,000 (the first midpoint probed) is found in 1 comparison, so 20 is a tight upper bound and 1 is the lower bound, exactly the O-and-Omega-but-not-Theta situation insertion sort is in, just with a much thinner best-case family.

Trade-offs and pitfalls

A common mistake is announcing "Theta" for an algorithm when only an upper bound (worst-case Big-O) has actually been shown, and note that this trap catches textbook examples too: "binary search is $\Theta(\log n)$" is true of its worst case and of unsuccessful search, but false of the algorithm over all inputs, because a target at the first probed midpoint costs 1 comparison at any n; another is treating Big-O as a complete performance description when it says nothing about the lower bound, so an algorithm claimed O(n) could secretly always run much faster. Omega is most often about the PROBLEM's inherent difficulty (like the n log n sorting lower bound), and conflating that with "my particular algorithm's best case" is a frequent interview slip. Finally, remember that these classifications say nothing about constants: comparing a $0.5n$ algorithm against a $0.1 \cdot n \log n$ algorithm directly shows how a small constant can still lose once n passes a modest threshold (here, n=32), which asymptotic notation by design does not tell you.

Approach. Cache blocking (tiling) restructures the three nested loops of matrix multiplication so that instead of streaming through entire rows/columns of $A$ and $B$ (which for large $N$ do not fit in L1/L2), the computation works on small $T \times T$ tiles that DO fit in a fast cache level. Each tile of $A$, $B$, and $C$ is loaded once and reused for all the arithmetic inside that tile before moving to the next tile, so the same cache line is reused many times instead of being evicted and re-fetched from a slower cache level or DRAM.

Choosing the tile size. Three $T \times T$ tiles of 4-byte floats (one each from $A$, $B$, $C$) must fit inside the target cache:

For a typical 32 KB L1 data cache this bounds $T$ at roughly 52; in practice engineers round down to a power-of-two-friendly size (e.g. 32) that also divides evenly into $N$ and aligns well with SIMD (Single Instruction, Multiple Data: one CPU instruction that
operates on several data elements at once) register widths, trading a little cache headroom for simpler, vectorizer-friendly code.

// Blocked matmul: C = A x B, all N x N, row-major. T is chosen so that
// 3 tiles of size T x T (one from A, B, C) fit in L1.
void matmul_blocked(const std::vector<float>& A, const std::vector<float>& B,
                     std::vector<float>& C, int N, int T) {
    std::fill(C.begin(), C.end(), 0.0f);
    for (int ii = 0; ii < N; ii += T)
      for (int jj = 0; jj < N; jj += T)
        for (int kk = 0; kk < N; kk += T)
          // Inner three loops stay inside one T x T tile of A, B, C.
          for (int i = ii; i < std::min(ii + T, N); ++i)
            for (int j = jj; j < std::min(jj + T, N); ++j) {
              float sum = C[i * N + j];
              for (int k = kk; k < std::min(kk + T, N); ++k)
                sum += A[i * N + k] * B[k * N + j];
              C[i * N + j] = sum;
            }
}

Run against a naive triple-loop version on a 128x128 matrix with a pinned seed (srand(42)), the blocked version reproduces the identical result:

N=128, assumed L1=32768 bytes, chosen tile size T=52 (3*T*T*4B = 32448 bytes <= 32768)
max |naive - blocked| = 0.000000
results match: true

Key points. The tiling only changes the order of the same $O(N^3)$ multiply-adds, so correctness is unaffected by construction (blocked and naive agree exactly). The gain is entirely from reuse: without tiling, each element of $B$'s column is re-fetched from DRAM on every row of $A$ once the matrices exceed the cache; with tiling, a tile of $B$ is loaded once and reused for every row inside that tile before eviction. Qualitatively this collapses a large share of what would otherwise be DRAM-latency-bound accesses into L1-latency-bound accesses, which is where most of the runtime improvement on large matrices comes from. The same reuse principle underlies related techniques: cache-oblivious recursive blocking (which tiles at every level without a fixed $T$), and blocking a matrix transpose in place to avoid the same "stream past the cache" problem when swapping rows and columns. It also connects directly to convolution: deep-learning frameworks routinely lower a convolution to a matmul (im2col), so the same tile-size-vs-cache-size reasoning drives convolution kernel performance too.

Complexity. Asymptotic time remains $O(N^3)$ and space $O(N^2)$ for the matrices themselves (plus $O(1)$ extra for tiling indices); tiling changes the constant factor and memory-access pattern, not the Big-O class.

Edge cases. $N$ not a multiple of $T$ (handled above via std::min clamping each tile's bound); very small $N$ where $N < T$ degenerates to the naive algorithm; and a tile size chosen too large for the actual hardware cache, which silently reintroduces the same eviction problem tiling was meant to fix.

Approach

A prefix sum (cumulative sum) at index i is the sum of all elements from index 0 through i. Compute it in a single left-to-right pass carrying a running total, either into a NEW list (leaves the input untouched) or by overwriting the input in place (saves memory but destroys the original values).

from typing import Iterable, Iterator, List


def prefix_sums(nums: List[int]) -> List[int]:
    result = [0] * len(nums)
    running = 0
    for i, x in enumerate(nums):
        running += x
        result[i] = running
    return result


def prefix_sums_in_place(nums: List[int]) -> List[int]:
    running = 0
    for i in range(len(nums)):
        running += nums[i]
        nums[i] = running
    return nums


class StreamingRunningSum:
    """O(1) memory: keeps only the running total, emits each cumulative
    value as it arrives instead of materializing the whole array."""

    def __init__(self) -> None:
        self._running = 0

    def feed(self, values: Iterable[int]) -> Iterator[int]:
        for x in values:
            self._running += x
            yield self._running


data = [3, 1, 4, 1, 5, 9, 2, 6]
out = prefix_sums(data)
print("prefix_sums:      ", out)
print("input unmodified: ", data)

data_copy = list(data)
print("prefix_sums_in_place:", prefix_sums_in_place(data_copy))

streamer = StreamingRunningSum()
print("streamed cumulative values:", list(streamer.feed(data)))

Output:

prefix_sums:       [3, 4, 8, 9, 14, 23, 25, 31]
input unmodified:  [3, 1, 4, 1, 5, 9, 2, 6]
prefix_sums_in_place: [3, 4, 8, 9, 14, 23, 25, 31]
streamed cumulative values: [3, 4, 8, 9, 14, 23, 25, 31]

Complexity

Both prefix_sums and prefix_sums_in_place are O(n) time. prefix_sums uses O(n) extra space for the output list; prefix_sums_in_place uses O(1) extra space beyond the input, at the cost of destroying the caller's original values, only acceptable when nothing else needs them afterward.

Streaming adaptation

For input too large to fit in memory, drop the idea of materializing the whole prefix-sum array and instead carry forward only the running total, exactly what StreamingRunningSum does, using O(1) memory regardless of how many values pass through. The trade-off: once a value has streamed past, you can't ask "what was the prefix sum at position 500,000?" without replaying from the start, since nothing was stored. If arbitrary past queries are genuinely required (not just "consume once, emit as you go"), the fix is a different data structure entirely, a Fenwick tree (binary indexed tree) over a bounded key range for O(log n) point updates and prefix queries, or periodic checkpointing of the running total to disk every K elements so a query can seek to the nearest checkpoint instead of replaying everything from position zero.

Edge cases

An empty input list returns an empty list (and the streaming generator simply yields nothing). Python integers have arbitrary precision, so summing very large or very many values never overflows the way it would in a fixed-width integer language like C++ or Java, worth mentioning explicitly if the interviewer is probing a language where overflow is a real concern.