Time and Space Complexity Analysis Questions

Direct answer: A sequence of $n$ append operations on a doubling dynamic array costs $O(n)$ total time, even though any single append can cost $O(n)$ in the worst case (when it triggers a resize) - so the amortized cost per append is $O(1)$. The proof works because expensive resizes happen exponentially less often as the array grows.

Structured elaboration - aggregate method

Assume the array starts at capacity 1 and doubles (1, 2, 4, 8, ..., ) whenever it's full. Consider $n$ appends. A resize happens when the array is full, i.e. at sizes $1, 2, 4, 8, \ldots$ (each resize copies all current elements to new storage). The total cost of all copying across $n$ appends is:

(a geometric series where each term is less than double the previous, so it sums to less than twice the largest term, which is itself less than $2n$). Add the $n$ "regular" O(1) insertions themselves, and total cost is $O(n) + O(n) = O(n)$. Dividing by $n$ operations gives $O(1)$ amortized cost per append.

Structured elaboration - accounting (banker's) method

Charge each append an amortized cost of $3$ (a constant): $1$ pays for the actual insertion, and $2$ are banked as credit on the newly-inserted element. When a resize happens (doubling from capacity $k$ to $2k$), it needs to copy $k$ elements - and exactly $k$ elements (those inserted since the last resize) are each carrying a banked credit of $2$, more than enough to pay the $k$ copies. The credit balance never goes negative, which is the proof obligation for the accounting method: since a constant amortized charge per operation covers all real costs including resizes, the true total cost over $n$ operations is $O(n)$.

Worked example

Trace $n = 8$ appends starting from capacity 1, showing real cost per append:

Total real cost: $1+2+3+1+5+1+1+1 = 15$. Over 8 appends, that's $15/8 \approx 1.9$ - a small constant, matching the $O(1)$-amortized claim (verified by direct summation, not an asymptotic hand-wave). The worst-case single append (append #5, cost 5) is far above the average, but the average stays bounded and does not grow with $n$: extending the trace to $n=16$ gives total cost $15 + 8(\text{copy}) + 8(\text{insert}) = 15+16=31$, and $31/16 \approx 1.94$ - essentially unchanged, confirming the ratio converges to a constant rather than growing.

Trade-offs & pitfalls

• A single append is NOT $O(1)$ worst-case - it's $O(n)$ worst-case, $O(1)$ AMORTIZED. Conflating these is the most common error; a latency-sensitive system doing one append per request can still see occasional O(n) latency spikes even though the aggregate throughput is fine.
• The proof depends critically on GEOMETRIC growth (doubling, or any fixed ratio > 1). Growing by a fixed constant (e.g. always +1 slot) gives $O(n)$ amortized per append (i.e. no better than the worst case), because the total copying work becomes $1+2+\cdots+n = O(n^2)$ - the geometric-series trick collapses.
• The accounting-method credit argument generalizes to any operation with occasional expensive rebalancing (hash-table resize, splay-tree rotations) - it's worth internalizing the credit-banking pattern, not just this one proof.

Direct answer: HNSW (Hierarchical Navigable Small World graphs) gives logarithmic-ish query time ($O(\log N)$ empirically, via greedy graph traversal across hierarchical layers) with strong recall but higher memory and index-build cost; IVF+PQ (inverted file index with product quantization) compresses vectors aggressively for much lower memory at the cost of recall, using a coarse clustering to restrict search to a subset of the data; LSH (locality-sensitive hashing) gives probabilistic sub-linear query time with weaker recall guarantees than either, but simpler theoretical underpinnings and easy distributed/sharded implementation. All trade exactness for speed and memory versus brute-force O(N x d) linear scan.

Structured elaboration

• HNSW: builds a multi-layer graph where higher layers have progressively fewer nodes (a "skip list"-like structure over the vector space), allowing search to start at a sparse top layer and greedily navigate toward the query's nearest neighbors, refining through denser lower layers. Query time is empirically close to logarithmic in N; build time is superlinear (each insertion involves graph-edge construction, roughly $O(N \log N)$ overall) and memory overhead is significant (storing the multi-layer graph structure, not just the raw vectors) - HNSW typically gives the BEST recall-per-query-latency trade-off among common ANN methods, at the highest memory cost.
• IVF+PQ: first clusters the dataset into coarse "cells" via k-means (the Inverted File index); a query only searches within the few nearest cells to its own location, avoiding the need to compare against the full dataset. Product Quantization further compresses each vector by splitting it into sub-vectors and quantizing each sub-vector to a small codebook, shrinking memory dramatically (often 10-30x smaller than storing raw float vectors) at the cost of the quantization introducing approximation error that reduces recall.
• LSH: hashes vectors such that similar vectors are more likely to collide into the same hash bucket than dissimilar ones (the opposite goal of a normal, collision-avoiding hash function); a query hashes and only checks the colliding bucket(s). Simpler to reason about and to shard/distribute (each hash table can live on a different machine), but typically needs multiple hash tables to achieve competitive recall, and its probabilistic guarantees are looser than HNSW's empirical graph-navigation quality.

Worked example

For 100 million 768-dimensional embeddings (a realistic large-scale semantic search setting): raw storage at float32 is $100\text{M} \times 768 \times 4\text{B} \approx 307\text{GB}$. IVF+PQ compressing each vector to, say, 64 bytes (a common PQ configuration) shrinks storage to $100\text{M} \times 64\text{B} = 6.4\text{GB}$ - roughly 48x smaller, making the difference between needing a multi-machine memory-resident index and fitting comfortably on a single large-memory machine. HNSW's graph overhead instead ADDS to the raw vector storage (typically an additional 30-100+ bytes per vector for the graph edges across layers, so roughly 100M x (3072+~60) bytes ≈ 313GB total) - HNSW does not compress the base vectors, so its memory footprint stays close to (or above) the raw storage size, trading memory for its superior recall/latency at query time.

Trade-offs & pitfalls

• Recall (fraction of TRUE nearest neighbors actually returned) versus latency versus memory is a three-way trade across all these methods - there's no universally "best" choice; the right one depends on which axis your system's constraints bind on hardest.
• Build/update cost matters for dynamic datasets: HNSW graph updates (inserting new vectors) are more expensive than IVF+PQ's (which can often just assign a new vector to its nearest existing cluster cheaply), a real consideration if the embedding collection changes frequently rather than being built once and queried many times.
• Hybrid approaches (e.g. IVF+HNSW combinations, or IVF+PQ with a re-ranking pass using exact distances on a small candidate set) are common in production to balance these trade-offs rather than committing to one pure method.

Direct answer: Greedy algorithms make the locally-best choice at each step and never reconsider it; they only produce a globally optimal result when the problem has the "greedy-choice property" (a locally optimal choice is always part of SOME globally optimal solution). Dynamic programming instead considers all relevant sub-solutions and combines them optimally, which is necessary whenever a problem has optimal substructure but LACKS the greedy-choice property - meaning an early locally-good choice can foreclose a better global outcome.

Structured elaboration

The classic contrast is coin change with a non-canonical coin system. With coins {1, 3, 4} and target 6: greedy (always take the largest coin that fits) picks 4, then 1, then 1 - three coins (4+1+1). The optimal answer is two coins: 3+3. Greedy fails here because taking the 4-coin first was locally attractive (it reduces the remaining amount fastest) but forecloses the better 3+3 solution - the greedy-choice property does not hold for this coin system. DP instead considers, for every amount from 0 up to the target, the best way to reach it using any allowed coin as the LAST coin used, guaranteeing the true optimum is found because every combination is implicitly considered via the subproblem recurrence, not just the first-glance-best one.

A cleaner illustration: weighted interval scheduling versus a naive earliest-finish-time greedy. Greedy-by-earliest-finish-time is actually PROVABLY OPTIMAL for the UNweighted version (maximizing the number of non-overlapping intervals selected) - the greedy-choice property genuinely holds there. But once intervals carry different WEIGHTS (values), earliest-finish-time greedy can pick a low-value interval that blocks a much higher-value overlapping one - here DP (considering, for each interval sorted by end time, the better of "skip it" versus "take it plus the best solution among intervals compatible with it") is required to guarantee optimality.

Worked example

Coin change with coins {1, 3, 4}, target 6, computed both ways:

def greedy_coin_change(coins, target):
    coins = sorted(coins, reverse=True)
    count = 0
    used = []
    remaining = target
    for c in coins:
        while remaining >= c:
            remaining -= c
            used.append(c)
            count += 1
    return count, used

def dp_coin_change(coins, target):
    INF = float('inf')
    best = [0] + [INF] * target
    choice = [None] * (target + 1)
    for amt in range(1, target + 1):
        for c in coins:
            if c <= amt and best[amt - c] + 1 < best[amt]:
                best[amt] = best[amt - c] + 1
                choice[amt] = c
    return best[target]

print(greedy_coin_change([1, 3, 4], 6))
print(dp_coin_change([1, 3, 4], 6))

Executed: greedy returns (3, [4, 1, 1]) - 3 coins. DP returns 2 - matching the known optimal 3+3 solution, confirming greedy's suboptimality on this coin system directly, not just by assertion.

Trade-offs & pitfalls

• Greedy IS the right (and much cheaper - typically O(n log n) for a sort plus a linear pass, versus DP's often O(n^2) or worse) choice whenever the greedy-choice property provably holds for your specific problem - don't reach for DP out of caution when a proof of greedy correctness is available (e.g. the unweighted interval scheduling case, or canonical coin systems like standard currency denominations, where greedy IS provably optimal).
• Recognizing whether a coin system is "canonical" (greedy-safe) in general is itself a non-trivial problem - when in doubt about a NEW, unfamiliar constraint set, default to DP unless you can specifically prove the greedy-choice property holds.
• A wrong greedy solution often looks superficially reasonable (3 coins isn't obviously wrong without comparing to the true optimum) - this is exactly why validating against a DP or exhaustive reference on small test cases is worth doing before trusting a greedy approach in production.

Direct answer: Inverting a dense $n \times n$ matrix via Gaussian elimination with partial pivoting costs $\Theta(n^3)$ time (specifically, approximately $\frac{2}{3}n^3$ floating-point operations for the elimination, comparable in order to matrix multiplication's leading constant) and $\Theta(n^2)$ space for the matrix itself (plus the augmented identity matrix during the standard inversion procedure, or an equivalent in-place scheme). For large $n$, explicit matrix inversion is usually avoided in favor of solving a specific linear system directly, or an iterative method, both of which can be substantially cheaper for the ACTUAL problem being solved.

Structured elaboration

• Gaussian elimination transforms the matrix to row-echelon form via a sequence of row operations, each pass eliminating one column below (and, for full reduction, above) the pivot - roughly $n$ passes, each touching $O(n^2)$ remaining entries, giving the $O(n^3)$ total.
• The LEADING CONSTANT (roughly $2/3$ for elimination alone, or higher when explicitly forming the full inverse rather than just solving one system) matters in practice - it's why "solve $Ax=b$" via LU decomposition (a byproduct of Gaussian elimination) plus forward/back substitution is preferred over first computing $A^{-1}$ explicitly and then multiplying by $b$: solving directly is both fewer total operations AND more numerically stable, since explicit inversion tends to amplify floating-point error more than solving a specific system does.
• For very large $n$, alternatives include iterative methods (like conjugate gradient for symmetric positive-definite systems), which can converge in far fewer than $n$ iterations for well-conditioned systems, each iteration costing $O(n^2)$ (a matrix-vector multiply) - potentially $O(kn^2)$ total for $k \ll n$ iterations, asymptotically better than $O(n^3)$ when $k$ stays small, though $k$ can grow with problem size/conditioning in the worst case.

Worked example

For $n = 10{,}000$: dense Gaussian elimination costs roughly $\frac{2}{3} \times (10{,}000)^3 \approx 6.7 \times 10^{11}$ FLOPs - a substantial but tractable computation on modern hardware with optimized (BLAS-backed) linear algebra libraries (which, similar to the matrix-multiplication case, achieve FLOP rates far above a naive implementation via cache-blocking and vectorization). If instead $A$ is SPARSE (common for large real-world systems, e.g. from a discretized PDE or a sparse graph Laplacian) with only $O(n)$ non-zero entries rather than $O(n^2)$, direct dense Gaussian elimination would be wasteful (it doesn't exploit the sparsity, and can even introduce "fill-in" - new non-zero entries appearing during elimination - degrading the sparsity), making sparse-aware direct solvers or iterative methods (which naturally exploit sparse matrix-vector multiplication's O(nnz) cost per iteration) the appropriate choice instead.

Trade-offs & pitfalls

• Never compute an explicit matrix inverse just to solve $Ax=b$ for a single (or even several) right-hand-side vector $b$ - LU-decomposition-plus-substitution is cheaper and more numerically stable; explicit inversion is really only justified when you need the inverse matrix ITSELF for further use (e.g. it appears explicitly, and repeatedly, in a downstream formula).
• Partial pivoting (swapping rows to bring the largest-magnitude candidate into the pivot position) is a NUMERICAL STABILITY requirement, not just a correctness nicety - without it, Gaussian elimination can produce wildly inaccurate results due to floating-point error amplification from small pivot values, even though the algorithm is "mathematically" the same either way.
• For very large or sparse systems, iterative methods' actual convergence rate (and thus effective total cost) depends heavily on the matrix's CONDITION NUMBER - a well-conditioned system converges fast, an ill-conditioned one may need many more iterations (or preconditioning) to reach acceptable accuracy, a real practical caveat beyond the clean asymptotic story.

Direct answer: A binary min-heap gives O(log n) insert, O(1) peek, and O(log n) extract-min. Building a heap from n unsorted elements via heapify (sift-down from the last non-leaf node upward) is O(n), not the O(n log n) you'd get from n individual inserts - a surprising result most candidates guess wrong.

Structured elaboration

• Insert: append at the end (O(1)), then sift up while the heap property is violated - at most O(log n) swaps (tree height).
• Peek: the root is always the minimum, O(1).
• Extract-min: swap root with the last element, remove the last element, then sift the new root down - O(log n).
• Build-heap (heapify): start from the last non-leaf node and sift each node down, working backward to the root. The insight for why this is O(n) rather than O(n log n): sift-down's cost is bounded by the HEIGHT of the subtree rooted at that node, and most nodes in a heap are near the bottom (leaves have height 0, and roughly half the nodes are leaves). Summing (number of nodes at height h) x (cost O(h)) over all heights gives a geometric-like series that converges to O(n), not O(n log n).

Worked example

(using the fact that $\sum_{h=0}^{\infty} h/2^h$ converges to a constant, 2). Verified numerically: instrumenting a heapify implementation to count total sift-down swaps on a randomly-shuffled array, for n = 1,000 / 10,000 / 100,000 / 1,000,000, gives swaps-per-n of roughly 0.73, 0.74, 0.74, 0.74 (essentially flat as n grows by three orders of magnitude), while swaps-per-(n log2 n) steadily drops (about 0.073, 0.055, 0.045, 0.037) - exactly the signature of O(n) growth, not O(n log n): the ratio to n stays constant, the ratio to n log n keeps shrinking.

Trade-offs & pitfalls

• The "n individual inserts = O(n log n)" alternative is also correct as an UPPER bound, just not tight - heapify is strictly better and is what real heap-construction (e.g. Python's heapq.heapify) uses.
• Extract-min and insert individually remain O(log n) even after an O(n) build - the O(n) result is specific to building from a full unsorted array, not to the per-operation cost afterward.
• Don't confuse "build-heap is O(n)" with "heap SORT is O(n)" - heapsort still needs n extract-min calls after the O(n) build, each O(log n), giving O(n log n) overall for the full sort.