Time and Space Complexity Analysis Questions

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: A hash table gives faster average-case lookup ($O(1)$ vs a BST's $O(\log n)$), but a balanced BST provides capabilities a hash table fundamentally cannot: ORDERED traversal, range queries ("all keys between X and Y"), and finding the next/previous key in sorted order - a hash table's whole design deliberately discards ordering information to achieve its O(1) average speed, so if your workload needs ANY of these ordered operations, a BST-backed structure (like a sorted map / TreeMap) is the right choice even though it's asymptotically slower for plain point lookups.

Structured elaboration

• Hash table: maps keys to bucket positions via a hash function specifically designed to SCATTER related keys unpredictably - this scattering is exactly what gives O(1) average lookup, but it also means there's no way to efficiently ask "what's the next key after this one" or "give me all keys in this range" without scanning the entire table, since sorted-order information simply isn't preserved by the hash-based layout.
• Balanced BST: maintains keys in sorted order via its tree structure - an in-order traversal yields keys in sorted order for free, floor/ceiling (next-smaller/next-larger key) queries are $O(\log n)$, and range queries (all keys in $[X, Y]$) are $O(\log n + k)$ for $k$ results - none of which a plain hash table supports efficiently.
• The complexity trade ($O(1)$ vs $O(\log n)$) is real but usually SECONDARY to the capability trade in practice - for the pure "is this key present / what's its value" access pattern, the constant-factor and asymptotic gap matters; but for any workload with an ordering requirement, the hash table simply cannot answer the question at all (not "slower," but "does not support this"), making the capability question the actually decisive one.

Worked example

For a data-science pipeline's feature-lookup dictionary (e.g. "look up this feature's metadata by name") where you only ever need exact-key retrieval, a hash table (Python dict) is unambiguously the right choice - there's no ordering requirement to sacrifice, so you get the O(1) speed for free. But for a time-series index needing "give me all events between timestamp A and timestamp B," a hash table CANNOT answer this without a full scan (checking every key against the range, O(n)) - only an ordered structure (a sorted list with binary search for static data, or a balanced BST / B-tree for data that changes) can answer it in $O(\log n + k)$, making the ordered structure the correct choice DESPITE its asymptotically worse plain point-lookup cost, because the actual query pattern needs the capability the hash table lacks entirely.

Trade-offs & pitfalls

• Don't default to a hash table purely out of habit ("O(1) is always better") - first ask whether ANY part of your access pattern needs ordering, range queries, or nearest-neighbor-in-sorted-order lookups; if so, that requirement should drive the structure choice ahead of the raw point-lookup speed comparison.
• Some languages/libraries offer BOTH in one structure (e.g. a sorted dict/treemap that maintains insertion or key order while still giving reasonably fast lookup) - worth knowing these exist as a middle ground when you need mostly-hash-speed with occasional ordered access.
• The $O(\log n)$ vs $O(1)$ gap matters more as $n$ grows very large and lookups dominate the workload - for smaller $n$ or infrequent lookups, the gap may be practically negligible, making the capability question even more clearly the deciding factor.

Direct answer: With memoization over both parameters $a, b \in [0, N]$, the function's time and space complexity are both $O(N^2)$: there are at most $(N+1)^2$ distinct $(a, b)$ pairs, each computed once and cached, and each computed state does $O(1)$ additional work beyond its (already-cached) recursive calls.

Structured elaboration

Without memoization, a recursive function over two parameters typically branches into a small constant number of recursive calls per invocation (say, 2-3, depending on the recurrence), giving exponential blowup because the same $(a, b)$ pair gets recomputed many times along different call paths.

With memoization:

• The state space is the set of all reachable $(a, b)$ pairs, bounded by $(N+1) \times (N+1) = O(N^2)$.
• Each distinct state is computed exactly once; on every subsequent call with the same $(a, b)$, the cached value is returned in $O(1)$.
• Total time is (number of distinct states) $\times$ (work per state, excluding recursive calls) $= O(N^2) \times O(1) = O(N^2)$.
• Space is the memo table itself, $O(N^2)$ entries, plus the recursion-call-stack depth, which is at most $O(N)$ if each call reduces $a+b$ (or similar) by a bounded amount - so the stack does not dominate the table.

Worked example

Take a concrete instance: $F(a, b) = F(a-1, b) + F(a, b-1)$ for $a, b > 0$, with base cases $F(0, b) = F(a, 0) = 1$ (this is the grid-path-counting recurrence, structurally identical to many DP-over-two-indices problems like edit distance or 2D grid counting). For $N = 3$:

def make_F():
    memo = {}
    calls = {"count": 0}
    def F(a, b):
        calls["count"] += 1
        if a == 0 or b == 0:
            return 1
        if (a, b) in memo:
            return memo[(a, b)]
        memo[(a, b)] = F(a - 1, b) + F(a, b - 1)
        return memo[(a, b)]
    return F, memo, calls

F, memo, calls = make_F()
result = F(3, 3)
print(result, len(memo), calls["count"])

Executed: F(3, 3) returns 20 (the number of monotonic lattice paths, matching $\binom{6}{3} = 20$), the memo table ends with exactly 9 entries (all $(a,b)$ pairs with $1 \le a, b \le 3$, confirming $O(N^2)$ distinct non-base states), and the memoized version makes 19 total function calls. Running the same recurrence with the cache removed entirely (identical logic, no memo dict) makes 39 calls for the same $F(3,3)$ - already noticeably more at this tiny $N$, and the gap widens combinatorially as $N$ grows, since the non-memoized call count follows the same exponential recursion-tree growth as naive Fibonacci, while the memoized version stays pinned to $O(N^2)$ states.

Trade-offs & pitfalls

• The "$O(N^2)$" bound assumes each state does $O(1)$ work beyond its recursive calls; if the per-state work itself scales with $a$ or $b$ (e.g. a loop inside the recursive step), multiply accordingly.
• Watch the recursion-DEPTH bound separately from the state-count bound - a poorly-designed recurrence could have depth $O(N^2)$ even though there are only $O(N^2)$ states, risking a stack overflow for large $N$ that a bottom-up (tabulated) version would avoid.
• If the parameters aren't bounded by a clean $[0, N]$ grid (e.g. one parameter can itself be a large derived value), re-derive the actual reachable state space before assuming it's the full product of the two ranges.

Direct answer: For group-by aggregation over data too large for memory, the single-machine approach mirrors external sort: partition the data by key (e.g. via hashing or an external sort on the key), so all records for a given group end up together, then stream through each partition accumulating the aggregate with O(1) additional memory per partition. The distributed version replaces "partition to disk" with "shuffle across the network by key" (the MapReduce/Spark groupByKey pattern), where cross-machine communication, not local I/O, becomes the dominant cost.

Structured elaboration

• Single-machine, external-memory: two viable strategies. (a) Hash-partition: apply a hash function to the group-by key, writing each record to one of $P$ partition files based on hash(key) % P, choosing $P$ large enough that each partition fits in memory; then process each partition independently in memory (build an in-memory hash map of group -> running aggregate). (b) Sort-based: external-sort the data by the group-by key (as in the external-sort survivor), then stream through the sorted output, aggregating each contiguous run of matching keys with O(1) memory (since once a key's records are no longer contiguous, that group is complete and can be flushed) - trading the sort's $O(n \log n)$-ish I/O cost for not needing to fit any single partition in memory.
• Distributed (MapReduce-style): the MAP phase emits (key, value) pairs; the SHUFFLE phase transfers all values for a given key to the same reducer machine (typically implemented as a hash-partition-and-network-transfer step); the REDUCE phase aggregates each key's values, now co-located on one machine. The cost model shifts: local computation is cheap, but the shuffle's network transfer volume (proportional to total data size, potentially with a skew multiplier if some keys are disproportionately large) is usually the dominant cost, alongside the DISK I/O many implementations use to spill intermediate shuffle data that doesn't fit in memory.

Worked example

For a distributed aggregation over 10 TB of data across a cluster: groupByKey shuffles the FULL 10 TB across the network (every value must reach its key's reducer), whereas reduceByKey/aggregateByKey (which pre-aggregates locally on each mapper BEFORE shuffling, exploiting the aggregate function's associativity, e.g. partial sums) shuffles only the much smaller PRE-AGGREGATED intermediate results - if there are, say, 10,000 distinct groups, the pre-aggregated shuffle volume could be orders of magnitude smaller than the raw 10 TB, even though the final result is identical. This is exactly why reduceByKey-style pre-aggregation is the standard recommended pattern over naive groupByKey for any aggregation that can be expressed associatively (sum, count, max, min - not "collect all values into a list," which cannot be pre-aggregated).

Trade-offs & pitfalls

• The single-machine choice between hash-partitioning and external-sort depends on whether the group-by key's cardinality and distribution are well-understood in advance (hash-partitioning needs a good estimate of $P$ to keep partitions memory-sized) versus whether you're willing to pay the sort's cost for a more uniform, skew-resistant approach.
• In the distributed case, SKEW (one key having vastly more records than others) can make a single reducer the bottleneck regardless of overall parallelism - this is the same skew problem the mapreduce_scale survivor addresses, and the mitigations (salting, partial pre-aggregation) apply here too.
• Choosing reduceByKey over groupByKey is a case where knowing the AGGREGATE FUNCTION's algebraic properties (associativity/commutativity) directly translates into a large, measurable performance win - this is a genuinely high-leverage piece of knowledge for anyone working with distributed aggregation frameworks.

Direct answer: Union-find (disjoint-set) maintains a partition of elements into disjoint sets, supporting find(x) (which set is $x$ in) and union(x, y) (merge two sets), both in amortized $O(\alpha(n))$ time when combined with union by rank and path compression - a bound so close to constant that $\alpha(n)$ is under 5 for any $n$ you will ever encounter, even up to the number of atoms in the observable universe.

Structured elaboration

• Union by rank (or size): when merging two trees, always attach the smaller/shallower tree under the root of the larger/taller one. Alone, this bounds tree height to $O(\log n)$, giving $O(\log n)$ per operation.
• Path compression: during a find(x) call, once you've walked up to the root, re-point every node visited along the way directly to the root. This flattens the tree for future lookups.
• Combined, the two optimizations interact so that the amortized cost per operation becomes $O(\alpha(n))$, where $\alpha$ is the inverse Ackermann function - the functional inverse of the famously fast-growing Ackermann function.

Worked example

The inverse Ackermann function grows so slowly that $\alpha(n) \le 4$ for every $n$ up to roughly $2^{2^{2^{2^{65536}}}}$ - a number of digits vastly larger than the number of particles in the observable universe (estimated around $10^{80}$). In every practical system, $\alpha(n)$ is effectively a constant no larger than 4 or 5, which is why union-find with both optimizations is described as "amortized nearly-constant" or "amortized O(1) in practice," even though the formally tightest bound is $O(\alpha(n))$, not literally $O(1)$.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:  # path compression
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1

uf = UnionFind(10)
for a, b in [(0,1),(1,2),(3,4),(2,3)]:
    uf.union(a, b)
roots = {uf.find(i) for i in range(5)}
print(len(roots))  # elements 0-4 should all be in one set

Executed: after the four unions, find(0) == find(1) == find(2) == find(3) == find(4) all resolve to the same root (the code prints 1, confirming a single merged component), while find(5) through find(9) remain in their own singleton sets - verifying the structure correctly tracks connectivity.

Trade-offs & pitfalls

• Without path compression, union by rank alone still gives $O(\log n)$ - a fine bound, but the combination is what earns the amortized-nearly-constant claim; don't assume either optimization alone gets you there.
• Union-find does NOT support efficient split (undo a union) - if your problem needs that, this is the wrong structure.
• find without path compression is not wrong, just slower - some implementations skip it for simplicity when $n$ is small enough that $O(\log n)$ is already fast.