Time and Space Complexity Analysis Questions

Direct answer: Cache locality means accessing memory in a pattern that keeps the CPU's cache lines full of USEFUL data, rather than repeatedly evicting and re-fetching from slower main memory. Two algorithms with identical Big-O complexity can differ by an order of magnitude or more in real performance purely based on whether their memory access pattern is sequential (cache-friendly) or scattered (cache-hostile) - array-of-structures (AoS) versus structure-of-arrays (SoA) is the canonical example.

Structured elaboration

• Array-of-structures (AoS): each record is stored as one contiguous struct ({id, name, score}), and an array of records places these structs one after another. Iterating over ALL records to read every field is cache-friendly (sequential access), but iterating to read just ONE field (say, score) across millions of records means the CPU loads an entire cache line's worth of struct data (including id and name, which you don't need right now) for every few records - wasting cache bandwidth on unused fields.
• Structure-of-arrays (SoA): each FIELD gets its own contiguous array (ids[], names[], scores[]). Iterating over just scores[] for a computation touches only relevant, densely-packed data - every byte loaded into cache is useful, and the CPU's hardware prefetcher can predict the purely-sequential access pattern far more effectively.
• The underlying mechanism: modern CPUs fetch memory in cache-line-sized chunks (commonly 64 bytes) and a cache miss (data not already in a fast cache) costs roughly 100-200x more cycles than a cache hit - so an access pattern that wastes cache-line capacity on unneeded data multiplies your effective memory traffic without changing the algorithm's Big-O class at all.

Worked example

Consider iterating over 10 million records, each with 4 fields (16 bytes total per struct: an 8-byte double score plus 8 bytes of other fields), summing only the score field:

• AoS: each cache line (64 bytes) holds 4 full structs, but only 8 of every 16 bytes per struct (the score) is useful - roughly 50% of loaded cache-line bytes are wasted on this specific access pattern (worse if there are more unrelated fields per struct).
• SoA: the scores array alone is fully packed doubles - every byte loaded into a cache line is a score value actually being summed, 100% cache-line utilization for this access pattern.

Both approaches are $\Theta(n)$ time to sum n scores - identical Big-O - but the SoA layout does meaningfully less total memory traffic for this specific operation (bounded above by the wasted-byte fraction in the AoS case), which running an actual benchmark on representative hardware would show as a real, reproducible, and often substantial (multi-x) wall-clock difference, growing with how many "irrelevant" fields sit alongside the one you're actually scanning.

Trade-offs & pitfalls

• SoA is not universally better - if your access pattern typically touches MULTIPLE fields of the SAME record together (e.g. "for this specific user, get id, name, and score all at once"), AoS's locality-per-record wins instead, since SoA would scatter that lookup across three separate arrays.
• The right layout is a function of your DOMINANT access pattern, not a universal rule - profile the actual query/iteration shape before choosing, and be aware that a system serving mixed access patterns may need both layouts (or a hybrid) for different code paths.
• This is exactly the kind of gap that "Big-O is not the whole performance story" is pointing at - a correct complexity analysis (both are Theta(n)) is necessary but not sufficient for predicting real-world performance; memory-layout awareness is the complementary skill.

Approach: The classic edit-distance (Levenshtein) DP fills an $(n+1) \times (m+1)$ table where cell dp[i][j] depends only on dp[i-1][j], dp[i][j-1], and dp[i-1][j-1] - the PREVIOUS row and the current row being built. Since you never need any row before the immediately-preceding one, you can discard all older rows and keep only two rows (or even one, with careful in-place updates), reducing space from $O(n \times m)$ to $O(\min(n, m))$ by always making the shorter string the one indexing the smaller (retained) dimension.

def edit_distance_space_optimized(a, b):
    if len(a) < len(b):
        a, b = b, a  # ensure b is the shorter string (columns = O(min(n,m)))
    n, m = len(a), len(b)
    prev = list(range(m + 1))
    for i in range(1, n + 1):
        curr = [i] + [0] * m
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
        prev = curr
    return prev[m]

Key points: prev holds the previous row; curr is built left-to-right using prev (row above), curr[j-1] (just-computed cell to the left in the same row), and prev[j-1] (diagonal) - exactly the three dependencies edit distance needs, none of which require any row older than prev. After finishing row i, prev is replaced with curr, discarding the now-unneeded older row.

Complexity: $O(n \times m)$ time (unchanged - every cell is still computed once), $O(\min(n, m))$ space (only two rows of the shorter dimension's length are ever alive at once) - down from the naive $O(n \times m)$ space of storing the full table.

Edge cases: one string empty (the loop correctly reduces to just counting insertions/deletions, matching the base-case row/column of the full table); equal strings (distance 0, verified by the diagonal-copy path never triggering a +1).

Worked example / execution verification

tests = [
    ("kitten", "sitting", 3),
    ("", "abc", 3),
    ("abc", "abc", 0),
    ("flaw", "lawn", 2),
]
for a, b, expected in tests:
    got = edit_distance_space_optimized(a, b)
    print(a, b, "->", got, "expected", expected, "OK" if got == expected else "MISMATCH")

Executed: all four test cases match their expected, well-known edit-distance values (kitten->sitting is the textbook example, distance 3), confirming the space-optimized version produces identical results to the full O(n*m)-space table.

Trade-offs & pitfalls

• The direct, unavoidable cost of this optimization: you can no longer reconstruct the actual sequence of edit OPERATIONS (insert/delete/substitute) that achieves the minimum distance, since that reconstruction (traceback) needs the FULL table, not just the final distance value. If you need the edit script (not just the distance number), you either keep the full table, or use a more advanced technique (Hirschberg's algorithm) that recovers the actual alignment in O(n*m) time but only O(min(n,m)) space via a divide-and-conquer strategy that recursively finds the optimal split point.
• This row-reduction trick generalizes to any DP whose recurrence only references the immediately-preceding "layer" (previous row, previous diagonal, etc.) - it's worth recognizing as a reusable pattern (checking a new DP's dependency structure for this property), not just memorizing it for edit distance specifically.
• In-place single-row variants (using just one array, with careful ordering to avoid overwriting a value before it's read) can push memory down further, but add real implementation subtlety and bug risk - the two-row version above is the more robust, readable default.

Direct answer: Memoization (top-down) recurses naturally from the original problem, caching each subproblem's result the first time it's computed and reusing it on repeat visits; tabulation (bottom-up) instead iteratively fills a table starting from the base cases up to the target, with no recursion at all. Both achieve the same asymptotic time complexity once the state space is fully covered, but they differ in recursion-depth risk, ease of implementation, and whether they compute EVERY subproblem or only the ones actually reachable from the original call.

Structured elaboration

• Memoization: write the natural recursive definition, add a cache (dict or array) check at the top of the function, and store the result before returning. Naturally only computes subproblems that are ACTUALLY reachable from the top-level call - if some large fraction of the theoretical state space is never visited for a given input, memoization skips that unreachable work entirely (a real advantage when the reachable subset is much smaller than the full grid).
• Tabulation: build the table iteratively, typically filling it in an order that guarantees each cell's dependencies are already computed (e.g. filling a 1D or 2D array left-to-right, or in order of increasing subproblem "size"). Always computes EVERY cell in the table, even ones that might not be needed for a specific query - but avoids recursion entirely, so there's no call-stack depth risk.
• Recursion depth: memoization inherits the recursion-depth risk discussed in the recursion-vs-iteration survivor - for a state space with deep dependency chains, memoization can hit a stack-overflow limit that tabulation, being purely iterative, never encounters.
• Naive vs memoized Fibonacci: naive recursive Fibonacci recomputes overlapping subproblems repeatedly, giving exponential O(2^n) time (specifically, following the Fibonacci sequence's own exponential-ish growth in call count); memoized Fibonacci caches each fib(k) the first time it's computed, so each of the n distinct subproblems is computed exactly once - O(n) time, with the recursion collapsing the exponential blowup entirely.

Worked example

import sys

def fib_naive(n, calls=[0]):
    calls[0] += 1
    if n <= 1:
        return n
    return fib_naive(n - 1, calls) + fib_naive(n - 2, calls)

def fib_memo(n, cache=None, calls=None):
    if cache is None:
        cache = {}
    if calls is None:
        calls = [0]
    calls[0] += 1
    if n <= 1:
        return n
    if n in cache:
        return cache[n]
    cache[n] = fib_memo(n - 1, cache, calls) + fib_memo(n - 2, cache, calls)
    return cache[n]

for n in (10, 20, 30):
    c1 = [0]
    fib_naive(n, c1)
    c2 = [0]
    fib_memo(n, calls=c2)
    print(n, "naive calls:", c1[0], "memoized calls:", c2[0])

Executed: for n=10, naive makes 177 calls versus memoized's 19; for n=20, naive makes 21,891 calls versus memoized's 39; for n=30, naive makes 2,692,537 calls versus memoized's 59. The naive call count grows exponentially (consistent with O(2^n)-ish growth, technically O(phi^n) for the golden ratio phi), while memoized calls grow LINEARLY (roughly 2n-1, since each of the n distinct values is computed once via one top-level call plus one cache-hit-avoided recursive call each) - a dramatic, directly-measured confirmation of the exponential-to-linear collapse memoization provides.

Trade-offs & pitfalls

• Prefer memoization when the reachable subproblem space is meaningfully smaller than the full theoretical grid (common for problems with input-dependent branching) - tabulation would waste work computing unreached cells.
• Prefer tabulation when recursion depth is a genuine risk (deep dependency chains) or when you specifically want to apply SPACE optimization (e.g. only keeping the last two rows of a table, as in the DP space-optimization survivor) - that kind of rolling-window space trick is far more natural to express in an iterative, ordered-fill tabulation than in a top-down memoized recursion.
• Both give the same asymptotic time complexity ONCE the full reachable state space is covered - the practical choice is about implementation ergonomics, recursion-safety, and space-optimization opportunities, not about one being fundamentally faster than the other in the covered-cells sense.

Direct answer: Dijkstra's complexity depends entirely on the priority-queue implementation: $O(V^2)$ with a plain array, $O((V+E)\log V)$ with a binary heap, and $O(E + V \log V)$ with a Fibonacci heap (the theoretically best, rarely used in practice due to large constants). A* uses the same underlying machinery as Dijkstra but adds a heuristic $h(n)$ estimating remaining distance to the goal, which - if admissible (never overestimates) and consistent (satisfies a triangle-inequality-like property) - guarantees the optimal path is still found while typically exploring far fewer nodes than Dijkstra by prioritizing promising directions.

Structured elaboration

• Array-based Dijkstra: finding the minimum-distance unvisited vertex is an $O(V)$ scan, done $V$ times, giving $O(V^2)$ - reasonable for dense graphs where $E \approx V^2$ anyway.
• Binary-heap Dijkstra: each extract-min is $O(\log V)$, and each edge relaxation may trigger a decrease-key (also $O(\log V)$, or handled via re-insertion with lazy deletion in many implementations), giving $O((V+E)\log V)$ - the standard choice for sparse graphs.
• Fibonacci-heap Dijkstra: decrease-key is $O(1)$ amortized, so the bound improves to $O(E + V \log V)$ - asymptotically best, but the large constant factors and implementation complexity of Fibonacci heaps mean binary heaps usually win in practice except at very large scale.
• A*: identical algorithmic skeleton to Dijkstra, but the priority queue orders by $f(n) = g(n) + h(n)$ (cost-so-far plus heuristic estimate to goal) instead of just $g(n)$. An ADMISSIBLE heuristic (never overestimates true remaining cost) guarantees A* still finds the optimal path; a CONSISTENT heuristic (satisfies $h(n) \le \text{cost}(n, n') + h(n')$ for every edge) additionally guarantees no node needs to be re-expanded once popped, matching Dijkstra's efficiency guarantees while exploring fewer nodes in the common case, because the heuristic actively steers the search toward the goal instead of expanding uniformly outward in all directions.

Worked example

Consider road-network routing where straight-line (Euclidean) distance to the destination is used as $h(n)$: it's admissible (straight-line distance never overestimates actual road distance, which must be $\ge$ straight-line) and consistent (the triangle inequality holds for Euclidean distance). On a grid or road network, this heuristic causes A* to expand nodes roughly in an ellipse oriented toward the goal, rather than Dijkstra's expanding circle in all directions - for a goal far from the source, this concretely means A* explores a small fraction of the nodes Dijkstra would, even though both are guaranteed to find the same optimal-cost path.

Trade-offs & pitfalls

• A* is only as good as its heuristic - a poorly-chosen or non-admissible heuristic can make it explore MORE nodes than Dijkstra (if it misleads the search) or, worse, return a suboptimal path (if it's not admissible).
• When there's no useful domain-specific heuristic available (e.g. an abstract graph with no geometric embedding), A* degenerates to Dijkstra (using $h(n) = 0$ everywhere is trivially admissible and consistent).
• Fibonacci heaps are a common "textbook-optimal, practically-never-used" answer - know the asymptotic bound but be ready to say WHY binary heaps usually win in real systems (much smaller constant factors, simpler implementation, better cache behavior).

Direct answer: Quantization reduces numeric precision (e.g. float32 to int8) to shrink memory and speed up compute on hardware with efficient low-precision arithmetic, typically 2-4x smaller/faster with modest accuracy loss. Weight pruning removes (zeros out) individual weights or structured blocks, reducing FLOPs and memory proportionally to sparsity achieved, but unstructured pruning needs specialized sparse-compute support to realize speed gains (structured pruning gets speedups on ordinary hardware more easily). Knowledge distillation trains a smaller "student" model to mimic a larger "teacher" model's outputs, achieving the student's own (smaller) native complexity - not a modification of the original model at all, but a genuinely different, smaller model trained to approximate the original's behavior.

Structured elaboration

• Quantization: int8 quantization typically gives ~4x memory reduction (32 bits to 8 bits) and often 2-4x compute speedup on hardware with native int8 support (many modern accelerators), at an accuracy cost that's usually small (often under 1-2 percentage points for well-calibrated post-training quantization) but can be larger for models sensitive to precision (small models, or specific layers like the first/last). Extreme quantization (4-bit, 2-bit, binary) pushes the compression further but with rapidly increasing accuracy risk, often requiring quantization-AWARE training (fine-tuning with quantization effects simulated) rather than simple post-hoc conversion.
• Weight pruning: removing weights below some importance threshold (magnitude-based pruning is the simplest common approach) can achieve high sparsity (50-90%+ of weights removed) with often-small accuracy loss, especially with fine-tuning after pruning. The catch: UNSTRUCTURED pruning (removing individual weights scattered throughout a matrix) doesn't translate to actual speedup on standard dense-matrix hardware, since the hardware still processes the full dense matrix shape - you need sparse-aware kernels/hardware to realize the FLOP reduction. STRUCTURED pruning (removing entire channels, neurons, or attention heads) gives a genuinely smaller dense matrix, realizing speedups on ordinary hardware, at typically a steeper accuracy cost for the same nominal sparsity level.
• Knowledge distillation: train a smaller student architecture (potentially far fewer parameters, a genuinely different architecture) to match the teacher's output distribution (often using the teacher's soft probabilities, not just hard labels, as richer training signal). The student's inference cost is whatever ITS OWN architecture natively costs - distillation is a TRAINING technique, not a post-hoc compression of the original model's weights, and can achieve larger effective compression ratios than quantization or pruning alone, at the cost of a full separate training run and generally the largest accuracy gap of the three techniques for aggressive compression targets.

Trade-offs & pitfalls

• These three techniques are complementary, not mutually exclusive - a common production pipeline distills to a smaller architecture, THEN prunes and quantizes the distilled model, stacking compression from each technique.
• "FLOPs reduced" and "memory reduced" don't automatically mean "latency reduced" - unstructured pruning is the clearest example (real FLOP reduction, often zero latency benefit without specialized sparse kernels); always verify the actual HARDWARE realizes the theoretical savings before claiming a latency win.
• Accuracy risk scales with how aggressive the compression target is for ALL three techniques - a senior answer should name that these are all points on a Pareto frontier (accuracy vs compression), not free lunches, and the right choice depends on where on that frontier the specific deployment constraint sits.