Time and Space Complexity Analysis Questions

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: A B-tree updates data in place with O(log n) writes but each write touches disk pages randomly, giving high write amplification; an LSM-tree (log-structured merge-tree) buffers writes sequentially in memory and periodically merges (compacts) them to disk, giving much lower write amplification and near-sequential write throughput, at the cost of higher read amplification (a read may need to check multiple levels/files) and background compaction overhead. Write-heavy workloads (time-series ingestion, event logging) favor LSM-trees; read-heavy or update-in-place workloads (traditional OLTP) favor B-trees.

Structured elaboration

• B-tree: a balanced tree structure where each node holds many keys (matching disk-page size); inserts/updates find the right leaf in O(log n) and modify it in place. Because each modification is a random disk write to wherever that leaf's page lives, sustained write-heavy workloads suffer from many small random I/Os - this is "write amplification" in the sense that the actual bytes written to disk per logical update can include page splits/rebalancing overhead.
• LSM-tree: writes go first to an in-memory buffer (memtable), which is periodically flushed as an immutable, sorted file (SSTable) to disk - always a SEQUENTIAL write, which disks (especially spinning disks, but also flash to a lesser extent) handle far faster than random writes. Reads must check the memtable plus potentially multiple SSTable levels (mitigated by bloom filters per SSTable to skip files that can't contain the key), giving read amplification. Background COMPACTION merges and reorganizes SSTables to bound the number of levels a read must check and reclaim space from overwritten/deleted keys - this compaction work is itself extra I/O (space amplification during compaction, and write amplification from data being rewritten during merges).

Worked example

Concretely: on a workload of continuous high-volume writes (e.g. ingesting a million events/second), a B-tree's random-write pattern quickly becomes I/O-bound on the disk's random-IOPS ceiling, while an LSM-tree's sequential-write pattern can sustain throughput close to the disk's raw sequential-bandwidth limit - which is typically far higher than its random-IOPS limit, especially on spinning disks (10-100x) and still meaningfully higher on SSDs. This is exactly why write-optimized stores (Cassandra, RocksDB, LevelDB, HBase) use LSM-trees, while traditional relational databases (PostgreSQL, MySQL's InnoDB) default to B-tree-family indexes, since OLTP workloads are more balanced or read-heavy and value predictable point-lookup latency over raw write throughput.

Trade-offs & pitfalls

• LSM-trees pay for their write advantage with read complexity: a point lookup may need to check the memtable, then several SSTable levels (mitigated but not eliminated by per-SSTable bloom filters), giving worse and less predictable read latency than a B-tree's guaranteed O(log n) single-path descent.
• Compaction is not free - it consumes background I/O and CPU that competes with foreground read/write traffic, and a poorly-tuned compaction strategy can cause write stalls or unbounded space growth ("compaction debt").
• Range queries favor B-trees (data is stored in sorted order in place, contiguous scan) somewhat more naturally than LSM-trees (data is fragmented across sorted-but-separate SSTables, though modern implementations handle range scans reasonably well via merged iterators).

Direct answer: Asymptotically, $O(n)$ always eventually beats $O(n \log n)$ for large enough $n$ - but "eventually" can be a very large $n$, and for realistic input sizes the algorithm with worse asymptotic complexity often wins in wall-clock time because of a smaller constant factor, better cache locality, or simpler code with less overhead per operation.

Structured elaboration

The crossover point between two algorithms with complexities $c_1 \cdot n \log n$ and $c_2 \cdot n^2$ (or $c_1 \cdot n \log n$ vs $c_2 \cdot n$) depends entirely on the constants $c_1, c_2$, which asymptotic notation deliberately hides. A textbook example: a cache-unfriendly $O(n)$ algorithm that jumps around memory randomly (e.g. following linked-list pointers) can lose to a cache-friendly $O(n \log n)$ algorithm that scans memory sequentially (e.g. an array-based sort), because a single cache miss can cost 100-200x more cycles than a cache hit, and that per-operation constant swamps the asymptotic advantage until $n$ is large enough for the raw operation-count difference to dominate.

Worked example

Take two hypothetical implementations of the same task: Implementation A runs in $c_1 \cdot n \log n$ with $c_1 = 2$ (low constant, good cache behavior), Implementation B runs in $c_2 \cdot n$ with $c_2 = 50$ (high constant, e.g. from heavy memory churn or a costly per-element allocation). Setting them equal to find the crossover:

For any $n$ below about 33.5 million, Implementation A ($n \log n$, low constant) is actually faster despite its "worse" asymptotic class; only past that threshold does Implementation B's better asymptotic complexity start to win. If your real workload's $n$ never approaches that threshold (very common - many production workloads operate on thousands to low millions of items), choosing based on asymptotic complexity alone would be the wrong call.

Trade-offs & pitfalls

• Never choose an algorithm purely by comparing Big-O classes without at least a rough sense of (a) the realistic $n$ for your workload and (b) whether the "better" algorithm carries hidden constant-factor costs (extra memory allocation, worse cache locality, more complex control flow).
• When comparing "$O(n \log n)$ with low constant factors" versus "$O(n)$ but high memory churn and cache misses," the practical decision method is: benchmark both at your actual expected data scale, don't reason from asymptotics alone - and re-benchmark if $n$ is expected to grow substantially, since the crossover point is real and will eventually flip the decision.
• This is exactly why "premature optimization" toward asymptotically-optimal but complex algorithms can backfire: a simpler, cache-friendly algorithm with a worse Big-O class is often the right engineering choice at realistic scale, and revisiting the choice if $n$ grows is cheaper than over-engineering upfront.

Direct answer: Full-batch gradient descent computes the gradient over the ENTIRE dataset of size N before each update - O(N) work per step, but very few steps needed since each step's gradient is exact. Pure SGD (batch size 1) computes a gradient from a single example - O(1) work per step, but needs many more steps and each step's gradient is a noisy, high-variance estimate. Mini-batch SGD (batch size b) is the practical middle ground, O(b) work per step with gradient variance that decreases as $1/\sqrt{b}$, and - critically for modern hardware - the per-step work is highly PARALLELIZABLE across the batch dimension on a GPU, which is why throughput doesn't simply plateau immediately as batch size grows from 1.

Structured elaboration

• Per-step cost: proportional to batch size b (O(b) forward+backward work), true for all three variants (full-batch is simply b=N, pure SGD is b=1).
• Gradient variance: averaging over b independent samples reduces the VARIANCE of the gradient estimate by a factor of b (standard error shrinks as $1/\sqrt{b}$) relative to a single-sample gradient - this is why larger batches give a more accurate (lower-variance) estimate of the true full-dataset gradient direction, at the cost of more compute per step.
• GPU throughput and batch size: a GPU has a large but FIXED amount of parallel compute capacity; for small batch sizes, the GPU is under-utilized (idle compute units, since there isn't enough parallel work to fill them), so increasing batch size increases THROUGHPUT (examples processed per second) roughly linearly at first. Past some batch size, the GPU's compute units are fully saturated, and further batch-size increases no longer improve throughput per unit time (you're now compute-bound, not parallelism-starved) - this is why throughput plateaus, not because the underlying O(b) per-step cost changes, but because the WALL-CLOCK cost of processing b examples stops decreasing per-example once hardware parallelism is maxed out.

Worked example

Consider a GPU with enough parallel compute to fully utilize itself at batch size 256 for a given model. At batch size 32, the GPU processes each step in roughly the SAME wall-clock time it would take at batch size 256 (both are "cheap enough" to fit within one wave of parallel execution, dominated by fixed per-step overhead like kernel launch latency, not by the actual per-example compute) - so throughput (examples/second) at batch 32 is roughly 8x lower than at batch 256, purely from underutilizing available parallelism. Increasing batch size from 256 to 1024 (4x), once the GPU is already saturated at 256, roughly QUADRUPLES the wall-clock time per step (now truly compute-bound, scaling with actual work) while processing 4x the examples - so throughput stays roughly flat past this point, confirming the plateau.

Trade-offs & pitfalls

• Very large batch sizes, beyond the GPU-saturation throughput benefit, introduce their own OPTIMIZATION-QUALITY trade-off separate from the raw throughput question: overly large batches can generalize worse (a well-documented empirical phenomenon, sometimes called the "generalization gap"), requiring learning-rate scaling and other adjustments to compensate.
• Memory, not just compute, constrains batch size in practice - larger batches need proportionally more memory for activations (as discussed in the dense-layer-complexity survivor), and can hit a hard memory ceiling well before hitting a compute-bound throughput plateau.
• The variance-reduction benefit of larger batches has DIMINISHING returns ($1/\sqrt{b}$, not $1/b$) - doubling batch size from 1024 to 2048 reduces gradient noise by only about 29% (since $1/\sqrt{2} \approx 0.71$), a much smaller relative improvement than the first doubling from 1 to 2, which is part of why very large batch sizes give diminishing optimization benefit even before hitting hardware throughput limits.

Direct answer: Optimal scheduling of dependent tasks across N workers to minimize makespan (total completion time) is NP-hard in general (it's a generalization of job-shop scheduling / multiprocessor scheduling, both classically NP-hard), so exact optimal solutions become computationally infeasible past a small number of tasks. In practice, a greedy heuristic like longest-processing-time-first (LPT) or critical-path-first, combined with respecting the dependency DAG via a topological-order constraint, gives a solution computable in polynomial time (typically O(n log n) for sorting plus O(n + edges) for the scheduling pass) that is provably within a bounded factor of optimal (LPT is within 4/3 of optimal for the classic multiprocessor scheduling problem without dependencies).

Structured elaboration

• Why it's NP-hard: even without any dependencies, minimizing makespan across N identical machines (partitioning tasks into N groups to minimize the maximum group sum) is the classic "multiprocessor scheduling" problem, a well-known NP-hard problem (closely related to the partition/subset-sum problem). Adding a dependency DAG (some tasks must finish before others start) only makes the search space more constrained, not easier - exact solutions require exploring an exponential number of valid orderings/assignments in the worst case.
• Longest-processing-time-first (LPT): sort tasks by duration descending, then greedily assign each task (in that order) to whichever currently-least-loaded worker is idle and dependency-eligible (all its prerequisite tasks are already scheduled/complete). Sorting is O(n log n); the assignment pass is O(n log W) if worker loads are tracked in a heap (W = number of workers), or O(n * W) with a naive scan - either way polynomial, a world apart from exponential exact search.
• Critical-path-first: prioritize tasks that sit on the longest dependency chain (the "critical path" through the DAG) first, since delaying a critical-path task directly delays the whole schedule; tasks off the critical path have more scheduling slack. Computing the critical path is a single O(V+E) pass over the DAG (longest path in a DAG, computable via topological sort plus dynamic programming), making this heuristic's overall cost also polynomial.

Worked example

LPT's classical approximation guarantee (Graham's bound, 1969, for the dependency-free case): the makespan produced by LPT is never worse than $\frac{4}{3} - \frac{1}{3W}$ times the optimal makespan, where W is the number of workers - meaning for a 2-worker case, LPT is guaranteed within roughly 17% of optimal, and this guarantee HOLDS regardless of the specific task durations, without ever needing to compute the true optimal for comparison. Adding dependency constraints breaks this exact bound (LPT with dependencies loses the clean approximation guarantee since a critical-path task might get delayed behind an unrelated long task), but it remains a widely-used, empirically strong heuristic in practice for exactly this reason: polynomial-time and consistently close-to-optimal on realistic task-duration distributions, even without a formal bound in the dependency-constrained case.

Trade-offs & pitfalls

• Recognizing "this is NP-hard" is itself valuable interview signal - it tells you and your team that chasing an exact optimal solution at scale is the wrong investment, and that evaluating heuristics against their approximation guarantees (or empirically, against realistic workloads) is the right frame.
• The dependency DAG constraint means a heuristic must ALSO respect topological ordering, not just balance load - a heuristic that ignores dependencies (like naive LPT without the eligibility check) can produce an invalid or badly-delayed schedule.
• For genuinely small task counts (say under 20-30), exact approaches (integer linear programming, or exhaustive branch-and-bound with pruning) become tractable again and can be worth using when the problem size allows it - "NP-hard" is a worst-case-scaling statement, not a blanket ban on exact methods at small scale.