Time and Space Complexity Analysis Questions

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: 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: Any comparison-based sorting algorithm requires $\Omega(n \log n)$ comparisons in the worst case. The proof models any comparison sort as a binary decision tree: since there are $n!$ possible orderings of the input and each leaf of the tree corresponds to one output ordering, the tree needs at least $n!$ leaves, and a binary tree with $n!$ leaves must have depth at least $\log_2(n!)$, which is $\Theta(n \log n)$ by Stirling's approximation.

Structured elaboration

• Model any comparison sort as a binary decision tree: each internal node is a single comparison ("is $a_i < a_j$?"), each leaf represents one final determined ordering (permutation) of the input.
• A correct sort must be able to produce every one of the $n!$ possible orderings for some input, so the tree needs at least $n!$ distinct leaves.
• A binary tree of depth $d$ has at most $2^d$ leaves, so we need $2^d \ge n!$, i.e. $d \ge \log_2(n!)$.
• By Stirling's approximation, $\log_2(n!) = \Theta(n \log n)$.
• The worst-case number of comparisons for ANY comparison-based algorithm equals the depth of the deepest leaf reached, so the worst case is $\Omega(n \log n)$ comparisons - this is a lower bound on every possible comparison-based algorithm, not just a property of one specific sort.

Worked example

For $n = 4$: $4! = 24$ possible orderings. $\log_2(24) \approx 4.585$, so at least 5 comparisons are needed in the worst case for any comparison sort of 4 elements (you can't do it in 4). Mergesort on 4 elements uses at most 5 comparisons in its worst case - matching the lower bound essentially exactly, which is why mergesort/heapsort are called "asymptotically optimal" comparison sorts.

Trade-offs & pitfalls

• The bound applies only to COMPARISON-based sorts - it says nothing about algorithms that use more information than pairwise comparisons.
• Counting sort ($O(n+k)$ for keys in range $[0,k)$) and radix sort ($O(d(n+k))$ for $d$-digit keys) beat $n \log n$ because they never compare two elements directly - they use the numeric VALUE of keys to bucket them, which is extra information a black-box comparison oracle doesn't have. This does not contradict the lower bound; it sidesteps its assumption entirely.
• Practical caveat: counting/radix sort's better asymptotic complexity assumes bounded/small key ranges or fixed-width keys; for arbitrary-precision or highly varied keys, the "$k$" or "$d$" term can dominate and comparison sorts remain the pragmatic choice.

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.

Direct answer: Hash join builds an in-memory hash table on the smaller table (O(m) time/space for a table of size m) and probes it with the larger table's rows (O(n) time), giving O(m+n) total when the smaller table fits in memory - typically the fastest option for equality joins. Sort-merge join sorts both tables (O(m log m + n log n)) then merges them in a single linear pass (O(m+n)), which is preferable when the inputs are already sorted (or need to be sorted for another reason anyway), or when memory is too limited to build a hash table on even the smaller side.

Structured elaboration

• Hash join: build phase constructs a hash table keyed on the join column from the smaller input (choosing the smaller table minimizes memory and build time); probe phase streams the larger input, looking up each row's join key in the hash table in O(1) average. Total: O(m) build + O(n) probe = O(m+n), plus O(m) memory for the hash table.
• Sort-merge join: sort both inputs by the join key (O(m log m) and O(n log n)), then walk both sorted streams with two pointers, advancing whichever is behind, emitting matches - O(m+n) for the merge itself. Total including sort: O(m log m + n log n).
• When memory is limited and even the smaller table doesn't fit for a hash join, EXTERNAL variants of both exist: external hash join partitions both inputs by a hash of the join key into buckets small enough to fit in memory, then hash-joins bucket-pairs; external sort-merge does an external merge sort (as in the external-sort survivor) on both inputs first.

Worked example

Joining a 10-million-row orders table against a 50,000-row users table on user_id: a query planner would build the hash table on the small users side (50,000 entries, easily fits in memory) and probe with the 10 million orders rows - total work roughly O(10,050,000), essentially linear in the larger table's size, with the hash table build being a rounding error. Sort-merge here would cost O(50,000 log 50,000 + 10,000,000 log 10,000,000) - both sorts, dominated by the larger table's O(n log n) sort, meaningfully worse than the hash join's linear total for this size skew. Sort-merge only becomes competitive (or preferable) if one of the inputs is ALREADY sorted on the join key (e.g. it's the output of an index scan or a prior sorted operation), in which case its sort cost is zero and it wins outright on a linear merge versus hash join's need to still build a hash table.

Trade-offs & pitfalls

• A query planner's choice between these (and nested-loop join, which is O(m*n) and only competitive for very small inputs or when an index makes the inner loop O(log n) per probe) depends on table sizes, available memory, existing sort order, and whether an index exists on the join key.
• Hash join's memory requirement (holding the smaller side entirely in memory) is its main constraint - if even the smaller table is too large, you must fall back to a partitioned (external) hash join or sort-merge.
• Sort-merge join naturally produces sorted output (useful if a downstream operation needs sorted data, like a subsequent GROUP BY or another sort-merge join), which hash join does not - a real secondary consideration beyond raw join cost.