Time and Space Complexity Analysis Questions

Direct answer: In both cases the asymptotic time complexity is $O(n)$ and space is $O(n)$ for the output (or $O(1)$ extra if written back in place) - looping over $n$ elements is linear regardless of container type. The practical performance, however, differs by one to two orders of magnitude because a NumPy vectorized operation executes the loop in compiled C over a contiguous memory block, while a Python-level for loop over a list re-enters the Python interpreter for every element.

Structured elaboration

for i in range(n):
    x = arr[i] * 2

(a) Plain Python list: each iteration does a bytecode-level index lookup, a multiplication, an assignment, and a loop-control check, all through the CPython interpreter's eval loop. Each of these steps has real per-element overhead (dynamic type dispatch, reference counting, bounds checking) that a compiled language wouldn't pay. Complexity: $O(n)$ time, with a relatively large constant factor $c_{\text{python}}$.

(b) NumPy ndarray with a vectorized op (arr2 = arr * 2): the multiplication is dispatched once to a compiled C loop (ufunc) that iterates over contiguous memory with no per-element Python overhead, benefiting from CPU-level SIMD instructions and predictable cache access. Complexity: still $O(n)$ time (you still touch every element once), but the constant factor $c_{\text{numpy}}$ is dramatically smaller.

Worked example

Both are $\Theta(n)$, so the ratio of actual runtimes is roughly $c_{\text{python}} / c_{\text{numpy}}$, a constant independent of $n$ (for $n$ large enough to amortize any fixed overhead). Timing this on a representative machine (n = 5{,}000{,}000):

import numpy as np, time

n = 5_000_000
lst = list(range(n))
arr = np.arange(n)

t0 = time.perf_counter()
out = [x * 2 for x in lst]
t_list = time.perf_counter() - t0

t0 = time.perf_counter()
out2 = arr * 2
t_numpy = time.perf_counter() - t0

print(t_list, t_numpy, t_list / t_numpy)

Running this snippet and timing both versions confirms the qualitative claim without needing to trust a specific number: the vectorized version is consistently, dramatically faster (comfortably an order of magnitude or more, driven by interpreter overhead per element versus one dispatch into a compiled loop), and - this is the part worth actually checking - if you double $n$ and re-time both, each individual runtime roughly doubles while their ratio stays about the same. That last observation is the real proof that both are $\Theta(n)$: the growth pattern with $n$ is identical for both, only the constant multiplier differs. Any specific wall-clock multiplier is machine- and Python-version-dependent and should not be treated as a portable fact; the reasoning (interpreter dispatch overhead vs compiled contiguous-memory execution) is what transfers.

Trade-offs & pitfalls

• Never claim vectorization changes the Big-O class - it doesn't; it changes the constant factor, sometimes dramatically, which is exactly why "same asymptotic complexity" and "wildly different real performance" are not contradictory.
• The gap narrows as per-element work grows (if each element required a complex, branchy computation not expressible as a NumPy ufunc, the interpreter-loop version's relative overhead shrinks).
• Never state a specific wall-clock multiplier as a portable fact; only the qualitative order-of-magnitude and the underlying reason (interpreter overhead vs compiled contiguous-memory execution) transfer across machines.

Direct answer: The roofline model plots achievable performance (FLOPs/second) against a computation's arithmetic intensity (FLOPs performed per byte of memory moved), with a "roof" formed by two ceilings: a flat ceiling at the hardware's peak compute throughput, and a sloped ceiling determined by peak memory bandwidth. A computation is COMPUTE-BOUND if its arithmetic intensity is high enough to sit under the flat compute ceiling; it's MEMORY-BOUND if its arithmetic intensity is low enough that the sloped memory-bandwidth ceiling is the binding constraint.

Structured elaboration

Arithmetic intensity $I = \frac{\text{FLOPs}}{\text{bytes moved}}$. The roofline's two ceilings:

For low $I$ (few FLOPs per byte moved - e.g. simply summing an array, 1 FLOP per 4-8 bytes read), the $I \times \text{Bandwidth}$ term is the binding constraint: you're MEMORY-BOUND, and adding more compute capability (a faster chip) won't help until you either increase $I$ (do more work per byte moved, e.g. via tiling/blocking to increase reuse) or increase available bandwidth. For high $I$ (many FLOPs per byte - e.g. a well-tiled matrix multiply, which reuses each loaded value many times), you eventually hit the flat compute ceiling: you're COMPUTE-BOUND, and only a faster compute unit (or lower-precision arithmetic, or fewer redundant FLOPs) helps.

Worked example

The question gives: matrix multiply requires $2n^3$ FLOPs and moves $O(n^2)$ elements of size 4 bytes (assume single-precision floats, and that with sufficient blocking each of the $n^2$ elements per matrix is read from main memory only once, a best-case bandwidth assumption). Arithmetic intensity:

(the factor of 3 accounts for reading matrices A and B and writing/reading the output C, each $n^2$ elements). Take a representative GPU with peak compute of 20 TFLOP/s and peak memory bandwidth of 900 GB/s. The ridge point (where the two ceilings cross) is at $I_{\text{ridge}} = \text{Peak FLOPs} / \text{Peak Bandwidth} = 20 \times 10^{12} / 900 \times 10^9 \approx 22.2$ FLOPs/byte. Setting $I = n/6 = 22.2$ gives $n \approx 133$: for $n$ larger than roughly 133 (with this idealized single-read-per-element assumption), the (well-tiled) matrix multiply is compute-bound; for smaller $n$, it would be memory-bound. This matches real-world experience: large matrix multiplies are compute-bound on modern accelerators (which is exactly why they benefit so much from more raw FLOP throughput, e.g. specialized tensor cores), while operations with inherently low arithmetic intensity (elementwise ops, simple reductions) remain memory-bound regardless of how fast the compute units are.

Trade-offs & pitfalls

• This calculation assumes an IDEALIZED memory-access pattern (each element read exactly once, via good tiling) - a naive, unblocked matrix multiply has much lower EFFECTIVE arithmetic intensity (repeated re-reads of the same data from memory), which is precisely why tiling (the roofline-adjacent technique from the earlier survivor) matters: it doesn't change FLOP count, but it increases effective arithmetic intensity by improving reuse, potentially shifting an operation from memory-bound to compute-bound.
• The roofline model is a useful FIRST-ORDER diagnostic, not a complete performance predictor - it ignores latency effects, cache-hierarchy nuances (L1 vs L2 vs L3 have different bandwidths), and assumes perfect overlap of compute and memory access, none of which hold exactly in practice.
• Different operations on the SAME hardware can sit on very different points of the roofline - profiling a real workload's actual arithmetic intensity (not just assuming from the algorithm's FLOP formula) is the correct way to diagnose whether a specific kernel is compute- or memory-bound before trying to optimize it.

Direct answer: An LRU (least-recently-used) cache combines a hash map (for O(1) key lookup) with a doubly linked list (for O(1) reordering and eviction) - a hash map alone can't track recency order in O(1), and a linked list alone can't look up a key in O(1); the combination gives each structure the job it's good at.

Structured elaboration

• A hash map alone gives O(1) get/put by key, but has no notion of "which key was used least recently" without an O(n) scan - you'd need to store and update timestamps, then scan all entries to find the minimum, which is O(n) per eviction.
• A doubly linked list alone naturally tracks recency (move a node to the front on every access, evict from the back), but finding a node by KEY to move it requires an O(n) linear search through the list.
• Combined: the hash map stores key -> node pointers into the linked list. get(key): hash-map lookup finds the node in O(1), then the node is unlinked and relinked at the front of the list in O(1) (doubly-linked, so both neighbors are known without a search). put(key, value): same O(1) lookup-and-move if the key exists, or O(1) insertion at the front plus (if over capacity) O(1) removal of the tail node, whose key is then also removed from the hash map.
• The critical design detail: the hash map's VALUE isn't the cached value directly - it's a pointer/reference to the linked-list NODE, so that once you've found the node via the hash map, you can splice it within the list in O(1) without any further lookup.

Worked example

Trace put(1,'a'), put(2,'b'), get(1), put(3,'c') on a capacity-2 cache:

1. put(1,'a'): list = [1] (front=back=1), map = {1: node1}.
2. put(2,'b'): list = [2,1] (2 is now most-recent, at front), map = {1: node1, 2: node2}.
3. get(1): hash lookup finds node1 in O(1); since node1 is not already at the front, unlink it and relink at front: list = [1,2]. Returns 'a'.
4. put(3,'c'): over capacity (2 items already), so first evict the tail (2, the least-recently-used): remove node2 from the list AND delete key 2 from the map. Then insert 3 at the front: list = [3,1], map = {1: node1, 3: node3}.

Key 2 was correctly evicted because it was least-recently used relative to the get(1) access that promoted 1 - both the eviction (tail removal) and the promotion (move-to-front) happen in O(1) because the linked list's structure means every splice only touches a constant number of neighboring pointers.

Trade-offs & pitfalls

• If you used a SINGLY linked list instead of doubly linked, moving an arbitrary node to the front would require knowing its predecessor to unlink it - which means an O(n) search, defeating the purpose. The "doubly" part is not incidental; it's what makes O(1) splicing possible.
• Many candidates correctly identify "hash map + linked list" but then can't explain WHY neither alone suffices - be ready to name the specific operation (find-by-key for the list, recency-tracking for the map) that the other structure covers.
• This same hash-map-plus-doubly-linked-list pattern generalizes to any "O(1) lookup plus O(1) reordering" requirement, not just LRU - it's worth recognizing as a reusable pattern (e.g. LFU (least-frequently-used) caches use a similar idea with an extra layer for frequency buckets).

Direct answer: Insert and delete are still $O(1)$ amortized under a doubling-on-grow / halving-on-shrink policy, PROVIDED the resize thresholds have enough of a gap between them (e.g. grow at load factor 0.75, shrink only below 0.25) - a naive symmetric threshold (grow above 0.75, shrink below 0.75) breaks the amortized bound entirely, because an adversary can trigger a resize on every operation by oscillating around the threshold.

Structured elaboration

The grow-side proof is the same aggregate/accounting argument as dynamic-array doubling. The shrink side needs its own argument: when the table shrinks from capacity $2k$ to $k$ (because load factor dropped below some threshold $t$), the shrink costs $O(k)$ to rehash the remaining elements into the smaller table. For the amortized argument to close, that $O(k)$ shrink cost must be "paid for" by the $\Omega(k)$ delete operations that had to happen to bring the load factor down that far since the last resize.

This is exactly why the shrink threshold must sit meaningfully below the grow threshold, not equal to it. If you grow at load factor 0.75 and shrink at load factor 0.75 (i.e. a single shared threshold), an adversary alternating insert-delete-insert-delete right at that boundary triggers a full resize on every single operation - each resize costs $\Theta(n)$, giving $\Theta(n)$ amortized cost per operation, not $O(1)$. This failure mode is sometimes called "thrashing."

Worked example

Simulate the thrashing failure directly: a hash table with a single threshold at load factor 0.5 (grow when exceeded, shrink when it drops back below), starting with 4 elements in an 8-slot table (load factor exactly 0.5), then alternately deleting and inserting one element:

def simulate(threshold_gap, ops=200):
    cap = 8
    size = 4
    resizes = 0
    grow_t, shrink_t = (0.75, 0.25) if threshold_gap else (0.5, 0.5)
    for i in range(ops):
        if i % 2 == 0:
            size -= 1
        else:
            size += 1
        load = size / cap
        if load > grow_t:
            cap *= 2
            resizes += 1
        elif load < shrink_t:
            cap = max(1, cap // 2)
            resizes += 1
    return resizes

print("shared threshold (thrashing):", simulate(False))
print("gapped thresholds (hysteresis):", simulate(True))

Executed over 200 alternating insert/delete operations: the shared-threshold version triggers 200 resizes (a resize on essentially every operation - exactly the thrashing failure), while the gapped-threshold version (grow at 0.75, shrink at 0.25) triggers 0 resizes, because the oscillation never crosses either boundary. This confirms the amortized bound depends on the gap between the thresholds ("hysteresis"), not just on having a shrink policy at all.

Trade-offs & pitfalls

• A hysteresis gap is the standard fix, but it means the table can sit at up to 2x-4x more memory than the current element count would strictly need, in exchange for the amortized guarantee - a real memory/latency-predictability trade.
• Some production hash-table implementations simply never shrink (only grow), sidestepping the thrashing risk entirely at the cost of never reclaiming memory after a large table empties out.
• This same "grow/shrink hysteresis" pattern generalizes beyond hash tables to any auto-scaling system (e.g. don't scale a server fleet down the instant load dips below the scale-up threshold) - it's worth recognizing as the general principle, not just a hash-table trick.

Direct answer: Recursion trades a cleaner, often more readable expression of a problem's self-similar structure for O(depth) call-stack memory and the risk of a stack overflow on deep inputs; iteration (with an explicit stack if needed) avoids that risk at the cost of sometimes-less-natural code. Tail-call optimization can eliminate the stack-growth cost for tail-recursive functions, but only in languages/runtimes that guarantee it (many mainstream languages, including Python and Java, do not).

Structured elaboration

• Stack depth: every recursive call adds a frame to the call stack (local variables, return address, saved registers) - for a recursion depth of $d$, that's O(d) memory, separate from any data structure the algorithm is building. A deep tree traversal (skewed, near-linear-depth tree) or a large factorial computed via naive recursion can hit the runtime's default stack-size limit (often ~1000 frames in Python without adjustment, or a few thousand to tens of thousands depending on frame size and platform stack size elsewhere) well before hitting any actual memory limit.
• Tail-call optimization (TCO): if a recursive call is the LAST operation in a function (nothing left to do after it returns), a compiler/runtime CAN reuse the current stack frame instead of pushing a new one, turning the recursion into loop-like constant stack usage. Crucially, this only happens if the language/runtime actually implements TCO - Python and Java notably do NOT (by design, in Python's case, to keep stack traces meaningful for debugging), while Scheme and some functional languages guarantee it. Never assume TCO applies without confirming the specific runtime supports it.
• Iterative conversion: replacing recursion with an explicit stack (a list/array you manage manually, pushing and popping state) gives the same logical traversal with memory usage you control directly - typically still O(depth) for the explicit stack, but as HEAP-allocated data rather than native call-stack frames, which usually has a much higher practical size ceiling and won't crash with a language-level stack-overflow error.

Worked example

A deep, heavily right-skewed binary search tree with 100,000 nodes (essentially a linked list in tree's clothing) recursively traversed depth-first would need roughly 100,000 stack frames - in CPython (default recursion limit 1000, though adjustable via sys.setrecursionlimit) this raises RecursionError well before completing; converting to an iterative traversal using an explicit Python list as a stack handles the same 100,000-deep traversal without issue, because Python lists grow on the heap (subject only to overall available memory, not the much smaller default call-stack limit).

Trade-offs & pitfalls

• Recursive code is often significantly more readable for genuinely tree-shaped or self-similar problems (e.g. tree traversal, divide-and-conquer algorithms) - don't reflexively convert to iterative for problems where recursion depth is naturally bounded and small (e.g. balanced-tree traversal on a tree with $O(\log n)$ depth for $n$ up to billions).
• If depth is bounded by input structure that COULD be adversarial or unbounded (user-supplied nested JSON, an untrusted tree structure), prefer iteration or increase the stack size deliberately - a stack-overflow crash triggered by attacker-controlled input depth is a real production incident category (and, in some languages/contexts, a security concern).
• Converting recursion to iteration mechanically (using an explicit stack that mirrors exactly what the call stack would have held) is a reliable, teachable pattern - it's worth practicing as a transformation, not just knowing it's "possible".