Time and Space Complexity Analysis Questions

Direct answer: Quickselect finds the k-th smallest element in expected O(n) time by partitioning like quicksort but recursing into only the ONE side that contains the target rank (instead of both sides, as quicksort does) - its worst case is O(n^2) with a poor pivot choice, but the median-of-medians pivot-selection strategy guarantees O(n) worst-case at the cost of a larger constant factor.

Structured elaboration

• Like quicksort, pick a pivot and partition the array so elements less than the pivot come before it and elements greater come after.
• Unlike quicksort, once partitioned, you know which side contains the k-th smallest element (compare k against the pivot's final index) - recurse into ONLY that side, discarding the other entirely.
• Because each recursive call operates on roughly half the previous size (with a good pivot), the total work forms a geometric series ($n + n/2 + n/4 + \cdots$) that sums to O(n), not O(n log n) - this is the key difference from quicksort, which must recurse into BOTH halves and thus sums to O(n log n).
• Worst case: an adversarial or unlucky pivot choice (always picking the smallest or largest remaining element) means each partition only shrinks the problem by one element, giving O(n) + O(n-1) + ... = O(n^2), identical in shape to quicksort's worst case.
• Median-of-medians: guarantees a pivot that is provably within the 30th-70th percentile of the current subarray (by recursively finding the median of medians of small groups), which bounds the worst case to O(n) - but the overhead of this more careful pivot selection makes its constant factor noticeably worse than simple random-pivot quickselect for typical inputs, so it's rarely used in practice outside of guaranteeing worst-case bounds for adversarial-input-resistant systems.

Worked example

Finding the median (n=1,000,001, k=500,000) with random-pivot quickselect: expected work is O(n) with a small constant (empirically close to 2n comparisons on average across many pivot choices), while the true worst case (vanishingly unlikely with a randomized pivot, but possible with a naive fixed-first-element pivot on adversarial/sorted input) would degrade to roughly $\binom{n}{2} \approx 5 \times 10^{11}$ comparisons - the gap between expected and worst case is enormous, which is exactly why RANDOMIZED pivot selection (not median-of-medians) is the standard practical choice: it makes the O(n^2) worst case exponentially unlikely to occur by chance, without median-of-medians' extra constant-factor overhead.

Trade-offs & pitfalls

• Randomized-pivot quickselect is the default real-world choice: expected O(n), simple to implement, and the adversarial worst case requires the attacker to know your specific pivot-selection randomness, which is infeasible if properly seeded.
• Median-of-medians is the answer when you need a hard WORST-CASE guarantee regardless of adversarial input (e.g. exposed to untrusted, potentially crafted data) - know that it exists and why it works, even though it's rarely the practical default.
• Quickselect is NOT stable and mutates (partitions) the input array in place unless you copy first - both worth flagging as a caveat if the caller needs the original order/array preserved.

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: 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: 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: $T(n) = 2T(n/2) + n/\log n$ resolves to $T(n) = \Theta(n \log \log n)$ via the recursion-tree method - the Master Theorem's Case 3 requires $f(n)$ to be POLYNOMIALLY larger than $n^{\log_b a} = n$, but $n/\log n$ is not polynomially larger than $n$ (it's actually smaller by a log factor, sitting in the gap between Case 1 and Case 2), so the theorem does not directly resolve this recurrence and a direct expansion is needed.

Structured elaboration

Expand the recursion tree for $T(n) = 2T(n/2) + n/\log n$: at depth $k$, there are $2^k$ subproblems, each of size $n/2^k$, each contributing $\frac{n/2^k}{\log(n/2^k)}$ work. Summing across all $2^k$ nodes at level $k$:

The recursion bottoms out at depth $k = \log_2 n$ (when subproblem size reaches 1). Total cost is the sum over all levels $k = 0$ to $\log_2 n - 1$:

(substituting $j = \log_2 n - k$). The inner sum $\sum_{j=1}^{m} \frac{1}{j}$ is the harmonic series, which is $\Theta(\log m)$. With $m = \log_2 n$, that's $\Theta(\log \log n)$. So:

Worked example

Numerically verify the harmonic-sum claim for a moderate $n$ using code (this checks the SUMMATION step of the derivation, which is where an error would most likely hide, not the full recurrence's exact asymptotic constant):

import math

def harmonic_growth_check(n_values):
    for n in n_values:
        m = int(math.log2(n))
        harmonic = sum(1.0 / j for j in range(1, m + 1))
        ratio = harmonic / math.log(m) if m > 1 else float('nan')
        print(f"n={n:>10}  log2(n)={m:>3}  H_m={harmonic:.3f}  H_m/ln(ln2·log2n)~{ratio:.3f}")

harmonic_growth_check([2**10, 2**16, 2**20, 2**24])

Executed: the ratio $H_m / \ln(m)$ stays within a narrow band (about 1.19 to 1.27) and trends slowly toward 1 as $n$ (and hence $m = \log_2 n$) grows across the tested range from $n=2^{10}$ to $n=2^{24}$ - consistent with the known asymptotic $H_m = \ln m + \gamma + o(1)$, which means the ratio converges to 1 but only very slowly (logarithmically) as $m$ grows. The important confirmation is that the ratio stays bounded rather than diverging or collapsing to zero, verifying the harmonic sum $H_m$ genuinely grows as $\Theta(\log m) = \Theta(\log \log n)$ and not, say, a constant or a polynomial - which is the load-bearing step in the derivation above.

Trade-offs & pitfalls

• This result differs from a naive "round $f(n) = n/\log n$ down to Case 2 and just call it $\Theta(n \log n)$" - that would be WRONG; the actual answer, $\Theta(n \log \log n)$, is strictly smaller than $n \log n$, because $f(n)$ being slightly smaller than the Case-2 watershed does have a real (if subtle) effect.
• This exact recurrence shape (Case-theorem gap, requiring recursion-tree or a generalized method) shows up in a handful of real divide-and-conquer algorithms with logarithmically-discounted per-level work; recognizing "the Master Theorem doesn't apply here" is itself the valuable signal, not just knowing the final answer.
• Always double check which of the two adjacent Master Theorem cases you're near, and verify with a recursion-tree sum rather than guessing which side the gap resolves to - the direction of the gap (smaller vs larger than the watershed) determines whether the answer trends toward Case 1's or Case 2's flavor.