Algorithmic Complexity & Code-Level Optimization Questions

Approach

Algorithm R keeps the first k items unconditionally, then for each subsequent item at 0-indexed position i (i >= k), draws a uniformly random integer j in [0, i]; if j < k, it replaces reservoir[j] with the new item, otherwise the new item is discarded. This gives every item seen so far an equal probability of ending up in the final k-sized sample, without ever needing to know the stream's total length in advance.

Code

import random

def reservoir_sample(stream_iter, k: int) -> list:
    reservoir = []
    for i, item in enumerate(stream_iter):
        if i < k:
            reservoir.append(item)
        else:
            j = random.randint(0, i)
            if j < k:
                reservoir[j] = item
    return reservoir


random.seed(0)
stream = list(range(1, 21))
sample = reservoir_sample(iter(stream), k=5)
print("stream:", stream)
print("sample of 5:", sample)

from collections import Counter
n_items, k, trials = 10, 3, 200_000
counts = Counter()
random.seed(123)
for _ in range(trials):
    counts.update(reservoir_sample(iter(range(n_items)), k))

print(f"empirical inclusion probability over {trials:,} trials (expect ~{k/n_items:.3f} each):")
for item in range(n_items):
    print(f"  item {item}: {counts[item]/trials:.4f}")

Output when run unchanged:

stream: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
sample of 5: [9, 2, 3, 6, 10]
empirical inclusion probability over 200,000 trials (expect ~0.300 each):
  item 0: 0.2992
  item 1: 0.3010
  item 2: 0.3002
  item 3: 0.3002
  item 4: 0.3010
  item 5: 0.2982
  item 6: 0.3003
  item 7: 0.2995
  item 8: 0.3007
  item 9: 0.2999

Key points

Every one of the 10 items lands in the size-3 sample close to 30% of the time across 200,000 trials, matching the theoretical k/n = 3/10 = 0.30 inclusion probability, which is the property the algorithm guarantees for every item, not just the ones seen first or last. The randomness has to be drawn fresh once per item after the first k, so the per-item cost is O(1) but not zero.

Complexity

Time: O(1) per stream item after the initial k are collected, so O(N) total for a stream of N items, with only ONE pass and no need to know N in advance. Space: O(k), fixed regardless of stream length.

Edge cases

If the stream has fewer than k items total, the reservoir simply ends up holding all of them, with no error. A k=0 reservoir stays empty throughout. Because each item needs an independent random draw, running this in multiple threads against shared stream state requires either a single-writer design or a thread-safe random source, since correlated or shared random state across threads can silently break the uniformity the algorithm otherwise guarantees.

Production framing

This is a common pattern for log sampling in production pipelines: you want a small, representative, uniform sample of an effectively unbounded log stream for debugging or metrics, without buffering the whole log or running a two-pass algorithm that would need to know the total count first. A single pass with O(k) memory makes it safe to run inline on a live, high-volume stream.

Direct answer. Amdahl's Law bounds speedup on a fixed-size problem as you add processors (strong scaling: same total work, more workers); Gustafson's Law instead assumes the problem grows to use the extra processors (weak scaling: more workers, proportionally more work each), and is the more realistic model for most machine learning training, where adding GPUs is typically paired with a larger batch size or dataset rather than solving the exact same fixed problem faster.

Structured elaboration: the two formulas.

where $P$ is the parallelizable fraction of the work and $N$ is the number of processors (GPUs here).

Worked example. With $P = 0.7$ (70% parallelizable) and $N = 8$ GPUs:

Amdahl's Law gives a much more pessimistic 2.58x because it assumes the sequential 30% stays a fixed amount of wall-clock time no matter how many GPUs you throw at the rest, so that fixed slice increasingly dominates. Gustafson's Law gives 5.9x because it assumes the 30% "sequential" portion (e.g. data loading, gradient synchronization setup) does not grow even as the parallel portion (the actual per-sample compute) scales up with a bigger batch, so the serial fraction shrinks in relative terms as more work is done per unit time.

Trade-offs & pitfalls: which law fits which scaling regime. Amdahl's Law is the right lens for strong scaling: "I have a fixed dataset and want to train on it faster by adding GPUs," where the total work is constant and any non-parallelizable overhead becomes a hard ceiling. Gustafson's Law is the right lens for weak scaling: "I have more GPUs, so I'll train on more data (or a bigger model) in the same wall-clock time," which describes most large-scale training workflows in practice, since teams scale up dataset size or batch size together with hardware rather than keeping problem size fixed. Neither law captures communication overhead explicitly (both treat the serial fraction as fixed); this is why measured speedup in distributed training is often below both curves' more optimistic numbers.

Checking either law against a measurement. Both formulas take $P$ as given, and on a real training job nobody hands you $P$: you infer it from timings, which means a prediction built on it is only as good as that inference. Because both laws are theoretical in this way, the standard way to sanity-check them against reality is to measure the empirical parallel efficiency directly:

where $T_1$ is single-GPU time and $T_N$ is $N$-GPU time for the same workload. Efficiency noticeably below 1 (e.g. dropping toward 0.6-0.7 well before $N$ gets large) signals real-world communication overhead (gradient all-reduce, synchronization stalls) that neither Amdahl's nor Gustafson's simplified serial-fraction model accounts for, and is the practical diagnostic to run alongside either formula rather than trusting the formula's prediction blindly.

Direct answer

All three approaches are O(n) in time complexity for a single pass over 100 million floats, the difference is entirely in the constant factor and in memory behavior, and that difference is large enough to be the whole decision. A pure Python loop pays per-element interpreter and object overhead; vectorized NumPy replaces that with one call into a compiled C loop over contiguous memory; Numba or Cython compile the loop itself, closing most of the remaining gap and sometimes beating NumPy when the transform doesn't reduce to one or two clean vectorized expressions.

(a) Pure Python loop

Each of the 100 million iterations pays Python bytecode dispatch overhead plus the cost of boxing: a Python float is a heap-allocated object (roughly three times the size of a raw 8-byte double once you include the object header), and a Python list stores pointers to those objects rather than the values themselves. That means the data isn't contiguous in memory: iterating the list involves chasing pointers scattered across the heap, which defeats CPU hardware prefetching and produces poor cache behavior on top of the per-element interpreter cost. This option is the correctness baseline, not a production candidate, at this data size.

(b) Vectorized NumPy

A vectorized NumPy expression dispatches ONE call into a compiled C loop operating on a single contiguous buffer of raw doubles (100 million floats at 8 bytes each is 800 MB). Sequential access over that buffer is exactly the pattern CPU hardware prefetchers and SIMD (single-instruction-multiple-data) execution are good at, so per-element overhead effectively disappears. The remaining cost is memory bandwidth and any temporary arrays an expression allocates: chaining several operations ((x * 2 + 1) ** 2) can materialize an intermediate 800 MB array per step unless written to reuse buffers (out= parameters or in-place operators).

(c) Numba or Cython

Both compile the LOOP itself to native code instead of relying on a library call: Numba JIT-compiles (Just-In-Time compiles: turns the function into native machine code the first time it actually runs, instead of ahead of time) a Python function at runtime (@njit), Cython compiles a statically-typed, Python-like source file ahead of time into a C extension. Either can match or beat NumPy specifically when the transform has per-element branching or state that doesn't reduce to one or two vectorized expressions, because a hand-written compiled loop can do the whole computation in a single pass without materializing NumPy's intermediate temporary arrays.

Expected speedups

The ranges below are order-of-magnitude shapes to expect, not a benchmark of record: the exact factors depend on the machine, the transform, and the NumPy build, which is why the benchmarking section follows. For a simple elementwise transform such as (x * 2 + 1) ** 2 over float64:

• Pure Python loop to vectorized NumPy: expect roughly two orders of magnitude, in the region of 50x to 150x. That is not a mystery number, it is the per-element interpreter and boxing overhead disappearing: the Python loop spends the large majority of its time on bytecode dispatch and object handling rather than on the arithmetic.
• Vectorized NumPy to a compiled Numba or Cython loop: usually a small factor, often between 1x (no gain at all) and about 3x, and the size of that factor is predictable from MEMORY TRAFFIC rather than from raw instruction speed. Both end up running compiled code over the same contiguous buffer, so the only structural difference is temporaries. At 100 million float64 the array is 800 MB, and the chained NumPy expression (x * 2 + 1) ** 2 materializes three intermediate 800 MB arrays, moving roughly 4.8 GB through the memory bus (read plus write for each of three passes), while a fused compiled loop reads 800 MB and writes 800 MB once, about 1.6 GB. The ratio, about 3x, is the ceiling on what fusion can buy you, and it is why the compiled win shrinks toward 1x for a single-operation transform and grows toward 3x for a long chain.
• Pure Python loop to a compiled loop: the product of the two, so several hundred times.
  Use these to decide whether a step is worth taking at all. Going from the Python loop to NumPy is almost always worth it at 100 million elements; going from NumPy to a compiled loop is worth it only when the chain is long enough, or branchy enough, for that 3x-at-best fusion win to matter more than the build and maintenance cost.

Benchmarking approach

Measure your own numbers rather than trusting the ranges above. Warm up before timing (Numba's JIT compiles on first call, so that compilation cost must be excluded from the steady-state measurement), run multiple repetitions on the SAME input to reduce measurement noise, and verify correctness (near-identical output within floating-point tolerance) across all three BEFORE comparing speed, a faster wrong answer is not a candidate. Measure peak memory alongside time, not just time, since the memory-versus-speed shape differs across the three options.

Criteria for choosing what to deploy

• If the transform is one or two vectorized NumPy expressions, prefer NumPy: no separate compiled build step, easiest for the whole team to read and modify, no JIT warm-up latency on process startup.
• If profiling shows the algorithm has data-dependent branching or NumPy is forced to allocate large temporaries the transform doesn't logically need, move to Numba first (smallest code change from a plain loop) or Cython if you need a distributable compiled artifact, tighter control, or interop with other C/C++ code.
• Weigh maintainability explicitly: fewer engineers on most teams are comfortable debugging Cython or JIT-compiled code than debugging NumPy, and Numba's cold-start compilation cost matters if the process is short-lived (for example, a serverless function). The fastest option only wins if the team can keep it correct after you've moved on.

Trade-offs and pitfalls

Reaching for Cython or Numba before establishing that NumPy genuinely can't express the transform cleanly adds build complexity for a win that may not exist; conversely, forcing an awkward transform into a single NumPy expression just to avoid a compiled step can produce code that allocates far more temporary memory than a straightforward compiled loop would.

Direct answer

For a sequence of length N and hidden size d, standard (dense) self-attention costs O(N^2 * d) time per layer and needs O(N^2 + N*d) memory per layer, because every one of the N tokens attends to every other token, producing an N x N attention-weight matrix that must be computed and, for training, kept for the backward pass. This quadratic-in-N term is what makes self-attention the bottleneck for long sequences: doubling the sequence length quadruples the attention-matrix compute and memory, while the feed-forward block scales only linearly in N.

Structured elaboration

• Where the time cost comes from: Q, K, V are each N x d matrices (one row per token). Computing the raw scores Q K^T is an (N x d) times (d x N) matmul, costing O(N^2 * d) multiply-adds. Softmax over each row is O(N^2). Multiplying the resulting N x N weights by V (N x d) is another O(N^2 * d). Per layer, time = O(N^2 * d).
• Where the memory cost comes from: Q, K, V and other activations are each O(N*d); the attention-weight matrix is O(N^2) PER HEAD, and a full multi-head layer computes one N x N matrix per head, so total attention-matrix memory across all heads is O(N^2 * H) for head count H, usually written O(N^2) treating H as a small constant. For training, this matrix generally needs to be retained for backpropagation unless a fused/recomputation-based attention implementation is used.
• Per-token cost: during autoregressive generation, producing one new token's attention output costs O(N * d) time, since it must attend to all N previous tokens, and summed over generating N tokens this reproduces the O(N^2 * d) total. Keep the d factor in the MEMORY side of this too, because that is where it is most often dropped. Three different per-token memory quantities get confused with each other: (a) the key/value cache GROWS by O(d) per layer per generated token, one key vector and one value vector, independent of N; (b) the cache that must be RESIDENT and read on that step is O(N * d) per layer, which is the number that actually bounds how long a context you can serve; (c) the attention scores for the new token are only O(N) per head, a single row rather than the full N x N matrix, which is precisely why decoding is memory-BANDWIDTH bound (it streams the whole O(N * d) cache to do O(N * d) arithmetic) while prefill and training are compute and activation bound. Concretely at d=768 in float32: the cache grows by 2 * 768 * 4 = 6,144 bytes per layer per token, and after 4,096 tokens holds 2 * 4096 * 768 * 4 = 25.2 MB per layer, roughly 302 MB across 12 layers, none of which appears in a parameter count.

Worked example

Take N=4096, d=768, 12 attention heads, float32 (4 bytes/value):

• QKV activation memory: 3 * N * d * 4 bytes = 3 * 4096 * 768 * 4 = 37,748,736 bytes, about 37.7 MB.
• Attention-weight matrix memory across all 12 heads: 12 * N^2 * 4 bytes = 12 * 4096^2 * 4 = 805,306,368 bytes, about 805 MB, roughly 21x the QKV activations at this N.
• At N=512 (8x shorter), the attention matrix shrinks by (512/4096)^2 = 1/64, to about 12.6 MB: a 64x reduction for an 8x shorter sequence. That is the quadratic scaling made concrete, and exactly why doubling context length is so much more expensive than doubling batch size, which scales activations only linearly.

Trade-offs and pitfalls

It is easy to say "attention is O(N^2)" and forget the d factor in the time complexity, which matters when comparing models with very different hidden sizes; the mirror-image slip is quoting the key/value cache as "O(N)" during decoding, which drops the same d factor and understates the cache by three orders of magnitude at a typical hidden size. It is also easy to under-count the attention-matrix memory, since it is an intermediate activation rather than an explicit weight tensor, so naive parameter-counting tools miss it entirely. This O(N^2) memory wall is exactly the motivation behind sparse or linear-attention variants (sliding-window, low-rank, kernel-based approximations) that trade some modeling capacity for sub-quadratic scaling, a distinct topic from deriving the baseline cost asked here.

Direct answer

LRU (least recently used) evicts whichever entry was accessed longest ago; LFU (least frequently used) evicts whichever entry has been accessed the fewest times overall. Both support O(1) average-case get and put with the standard implementation, a hash map plus a doubly linked list for LRU, or a hash map plus frequency buckets for LFU, so the real difference for session objects is not raw speed, it is which access PATTERN each one handles well or badly.

Structured elaboration

• LRU complexity: O(1) average for get and put, using a hash map (key to node) plus a doubly linked list ordered by recency; on access, unlink and re-insert the node at the front, an O(1) pointer operation.
• LFU complexity: O(1) average using the classic hash-map-of-frequency-buckets design, a hash map from key to node, a hash map from frequency count to a doubly linked list of keys at that frequency, and tracking the current minimum frequency. Each access moves a node to the next frequency bucket, O(1), but with meaningfully more bookkeeping per access than LRU.
• How a full scan hurts each: a single sequential scan of many session objects that will never be touched again, such as a batch audit job iterating every session, is the classic LRU-killer: each scanned key becomes most-recently-used and evicts genuinely hot session data, tanking hit rate right after the scan. LFU is naturally immune to this specific failure mode, since a one-time scan gives every scanned key a frequency of only 1, which will not outrank sessions already at high frequency.
• How a traffic spike hurts each: LFU has the opposite weakness, it is slow to adapt to a session that suddenly becomes hot, for example one tied to a viral shared link, since it starts at frequency 1 and must earn enough accesses to outrank long-lived, previously-popular sessions before LFU protects it. LRU adapts instantly, since one access makes the session most-recently-used and safe from the next eviction regardless of history.
• A hybrid: a common production compromise tracks both recency and frequency, for example a two-tier cache where a first access goes into a small probationary LRU segment and only gets promoted to a larger protected segment after a second access within some time window, resisting a one-time scan (a single-access key never leaves probation, so it cannot evict protected data) while still adapting quickly to genuinely new hot keys (promoted after just their second access, not after accumulating a high absolute frequency).

Worked example

A cache with room for 10,000 session objects, sitting in front of a store that holds 1,000,000 sessions, and a nightly audit job that reads every one of those 1,000,000 sessions once. The size relationship is the whole point: the scan set is 100 times the cache's capacity. A scan that only re-read the 10,000 sessions already resident would evict nothing at all under LRU, it would just permute the recency order, and under LFU it would add 1 to every resident key and leave the ranking unchanged. The damage comes from the 990,000 keys that were never in the cache.
Under plain LRU, each of those audit reads is a miss, and a miss gets ADMITTED at the most-recently-used end. After the first 10,000 misses the cache has already evicted every genuinely hot session, and it spends the rest of the scan churning through rows that will never be read again. Real traffic then resumes against a cache whose hit rate is near zero and has to refill it from scratch, a measurable dip after every nightly audit.
Under plain LFU, each of those 990,000 newly admitted keys enters at frequency 1 while the genuinely hot sessions already sit at much higher counts, so the audit rows become eviction candidates almost as fast as they arrive and the hot set survives the scan intact. Note the asymmetry that makes this a trade rather than a free win: the same frequency-1 entry point is exactly what makes LFU slow to protect a brand-new session that is about to become hot.

Trade-offs and pitfalls

LFU's extra bookkeeping, frequency buckets and minimum-frequency tracking, is a real, if modest, implementation and memory cost over LRU's simpler linked-list design, and LFU needs an aging or decay mechanism in practice, otherwise a key that was extremely popular last month but is now cold can sit protected by its accumulated historical frequency long after it stopped mattering, a failure mode LRU does not have. Choosing purely on this trade-off without measuring the actual access pattern, how common full scans versus sudden spikes are in the real workload, is a common mistake; the hybrid approach exists precisely because most real workloads mix both failure modes.