Algorithmic Complexity & Code-Level Optimization Questions

Direct answer

The naive nested-loop duplicate check is $O(n^2)$ time and $O(1)$ extra space; swapping in a hash set drops time to $O(n)$ average at the cost of $O(n)$ extra space. As a reviewer, that trade is usually worth making, except when memory is genuinely tight, the input arrives as an unbounded stream, or the check has to hold across multiple machines rather than one process.

Structured elaboration

The naive approach compares every element against every other element (for each i, scan all j past it looking for a match), doing roughly $n(n-1)/2$ comparisons in the worst case, $O(n^2)$, while using no extra memory beyond the input itself, $O(1)$ space. Replacing the inner scan with a hash set turns this into a single pass: for each element, check set membership (average $O(1)$) and insert it if new; total time becomes $O(n)$ average (the same $O(1)$-average/$O(n)$-worst-case caveat that applies to any hash table lookup applies here too), at the cost of $O(n)$ extra space to hold the set of seen elements.

When switching to a hash set is appropriate: whenever n is large enough that $O(n^2)$ is actually a problem (the crossover is much lower than people expect: even n in the low thousands makes millions of comparisons), and there's enough spare memory to hold a second copy's worth of the data as a set. This is the overwhelmingly common case for backend code reviewing a nested-loop duplicate check: it's usually a straightforward, low-risk improvement.

When you might avoid it:

• Memory constraints: if n is enormous (hundreds of millions of elements) and memory is the scarce resource rather than CPU time, materializing a full hash set of everything seen so far can itself become the bottleneck or exceed available RAM, in which case an approximate structure like a Bloom filter (trading a small false-positive rate for dramatically less memory) or an external, disk-backed dedup step may be more appropriate than an exact in-memory hash set.
• Streaming requirements: if the data arrives as an unbounded or very long-lived stream rather than a fixed array, a plain hash set held for the lifetime of the stream grows without bound, which is a memory leak in disguise; a windowed or time-bounded dedup structure (only remembering the last N seconds or N items) is usually what's actually needed instead of "just add everything to a set forever."
• Distributed consistency needs: if duplicates need to be detected across multiple machines or processes rather than within a single one, an in-process hash set on one node cannot see what another node has already processed; the check has to move to a shared store (a database unique constraint, a distributed cache, or a coordination service), which changes the complexity picture entirely, since now network round trips, not CPU cycles, dominate the cost, and the "just use a hash set" answer doesn't transfer directly.

Worked example

For n=10,000 elements: the naive approach does up to $10{,}000 \times 9{,}999 / 2 = 49{,}995{,}000$ comparisons in the worst case (no duplicates until the very end, or none at all), while the hash-set approach does about 10,000 hash operations, a difference of roughly four orders of magnitude in operation count for the exact same correctness guarantee, which is why this is one of the most reliably worthwhile "the code works but doesn't scale" fixes a reviewer will ever flag.

Trade-offs and pitfalls

The most common review-time mistake is recommending the hash-set fix reflexively without checking any of the three exceptions above; a nested loop over a genuinely small, bounded n (say, under a few hundred elements, run rarely) may not be worth the code-complexity or memory trade-off at all, since $O(n^2)$ with a tiny constant can still be faster in absolute terms than a hash set's larger per-operation constant for small n, which is the same "don't optimize before measuring" principle that applies to any performance decision.

Direct answer. For single-pair shortest-path queries on a graph the size of a national road network (30M nodes, 100M edges), plain Dijkstra's algorithm ($O(E\log V)$) is far too slow for an interactive, online routing service; bidirectional A* with a good admissible heuristic (one that never overestimates true remaining distance, e.g. straight-line distance divided by the network's maximum possible speed) narrows the search meaningfully, but the real production answer is neither: it is heavy offline preprocessing (contraction hierarchies or landmark-based bounds) that makes the online query itself touch a tiny fraction of the graph.

Structured elaboration.

• Dijkstra explores nodes in strictly increasing distance order from the source with no notion of "toward the destination," so for a long point-to-point query it can expand a search frontier covering a large fraction of the graph before reaching the target, an unacceptable amount of work to redo on every request.
• A* with an admissible heuristic biases the same expansion order toward nodes that look closer to the destination, shrinking the explored region considerably; running it bidirectionally (searching forward from the source and backward from the destination simultaneously) roughly halves the effective search radius from each side, since each search only needs to cover about half the distance.
• The termination rule is where bidirectional search is usually got wrong. You may not stop the moment the two frontiers touch. The first node both searches have scanned is generally not on the shortest path, because the two searches settle nodes in their own increasing-distance order and the true optimum can route through a node that one side has not settled yet. The correct rule is to keep a running best $\mu$ (the smallest $d_f(v) + d_b(v)$ over any node $v$ scanned by both directions, updated on every edge relaxation that closes a path), and to stop only when $\text{top}_f + \text{top}_b \ge \mu$, where $\text{top}_f$ and $\text{top}_b$ are the minimum keys still in the two priority queues. At that point no unexplored path can be shorter than $\mu$, so $\mu$ is provably optimal. Stopping at first contact is an easy way to ship routes that are quietly a few percent too long, a bug no test that only checks "a path was returned" will catch.
• Bidirectional A* additionally needs the two heuristics to agree with each other. Using $h_f(v) =$ estimated distance from $v$ to the target and $h_b(v) =$ estimated distance from the source to $v$ independently breaks the correctness argument, because the forward and backward searches are then effectively optimizing over two different reduced edge-weight functions and the stopping condition above no longer bounds anything. The standard fix is balanced (consistent) potentials, for example $p_f(v) = \tfrac{1}{2}(h_f(v) - h_b(v))$ and $p_b(v) = -p_f(v)$, which makes both directions see the same reduced costs at the price of a weaker (but still admissible) bound than either raw heuristic.
• Contraction hierarchies (CH): an offline preprocessing step that orders nodes by "importance" (roughly, how often shortest paths pass through them) and adds shortcut edges that let a query skip over long stretches of "unimportant" road automatically. An online query then only needs to search a small local neighborhood at each end plus a fast pass over shortcuts, turning what would be a graph-spanning search into one that touches a tiny, roughly-constant-relative-to-graph-size neighborhood.
• Landmark-based bounds (the ALT algorithm: A*, Landmarks, and the Triangle inequality): precompute exact distances from a small set of fixed landmark nodes to every other node offline, then use the triangle inequality between any node and a landmark to derive a much tighter heuristic lower bound online than straight-line distance alone provides, improving A*'s pruning without needing shortcut edges.

Estimating the three, in the units the service cares about. The comparison only becomes a decision once it is in milliseconds, so put a number on it with explicit assumptions rather than leaving it at "far too slow". Average degree is $100\text{M}/30\text{M} \approx 3.3$ edges per node. Assume a long cross-country query makes Dijkstra settle roughly half the graph, 15M nodes, and charge a deliberately optimistic 100 ns per settled node (a heap pop plus a scattered adjacency read, both cache-missing) and 20 ns per edge relaxation:

$$15\text{M} \times 100\text{ns} + (15\text{M} \times 3.3) \times 20\text{ns} \approx 1.5\text{s} + 1.0\text{s} \approx 2.5\text{s}$$

So plain Dijkstra lands in the seconds, three orders of magnitude outside an interactive budget, and this is a lower bound because it assumes a perfectly warm, perfectly laid out graph. Bidirectional A* divides that by whatever factor the heuristic shrinks the settled set by; a straight-line-over-max-speed bound is loose on a road network (roads are not straight, and almost the whole network is below the maximum speed), so even a generous factor of 10 leaves roughly 250 ms, which is still an entire core for four queries per second. Contraction hierarchies settle on the order of a few hundred to a few thousand nodes per query instead of millions, so at the same 100 ns per settled node the query lands well under a millisecond, and that four-to-six order of magnitude gap, not a constant-factor improvement, is what makes an online routing service feasible.

The same arithmetic prices the storage side of the trade. Landmark distances are the expensive one: 16 landmarks, 30M nodes, both directions, 4 bytes per distance is $16 \times 30\text{M} \times 2 \times 4 = 3.84$ GB of precomputed tables that must be resident to be useful. CH is cheaper: shortcuts commonly add on the order of the original edge count again, so roughly 100M extra edges at about 8 bytes each is under a gigabyte. That asymmetry is usually what decides between them once both are known to be fast enough.

Trade-offs for a backend routing service. Preprocessing (CH or landmarks) moves cost from "every query, every time" to "once, offline, amortized over all future queries" (amortized meaning the one-time preprocessing cost is spread thin across every query that follows, so its per-query share shrinks toward negligible the more queries the service answers), which is exactly the right trade for a service answering many queries against a mostly-static road network: query latency drops dramatically (from a search that could touch a meaningful fraction of 30M nodes to one touching a small local neighborhood), at the cost of a nontrivial offline build time and extra storage (shortcut edges in CH roughly increase edge count, commonly to a small multiple of the original graph). The real complication is that road networks are not static: live traffic changes edge weights continuously, and both CH and landmark bounds are built around the assumption that edge weights do not change, so a production system typically layers a lighter-weight, frequently-refreshed traffic adjustment on top of a preprocessed base graph rather than rebuilding the full preprocessing on every traffic update, and falls back toward plain bidirectional A* for edge cases (very fresh incidents) the preprocessing has not caught up with yet. Note that a weight increase from traffic is the dangerous direction: a CH shortcut caches a path whose cost only went up, so the stored shortcut is no longer a valid lower bound and the query can return a route that is no longer optimal, which is why the live-traffic layer is a correctness concern and not only a freshness one.

Direct answer
Naive ijk matrix multiplication has poor cache reuse (poor spatial locality: it fails to reuse data sitting near an address it just accessed) because its inner loop strides through the second matrix column by column, while a cache-aware blocked (tiled) version restructures the loops to operate on small sub-blocks that fit in cache together, so each loaded element is reused many times before eviction. The predicted reduction in cache misses is not a percentage, it is orders of magnitude for realistic cache sizes. The resulting runtime speedup is much smaller than that, and keeping those two numbers apart is most of the skill in this question.

Structured elaboration
Let cache capacity be $C$ words, cache line size $L$ words (each miss brings in $L$ consecutive words), and block size $B \times B$ chosen so three $B \times B$ tiles (one from each of the two input matrices and the output) fit in cache at once:

$3B^2 \le C \quad\Rightarrow\quad B \approx \sqrt{C/3}$

Naive ijk. For $n$ large enough that the working set does not fit in cache, the matrix being multiplied on the right is accessed column-wise in the inner loop: successive iterations jump $n$ elements in memory, so a cache line brought in for that access is used once and evicted before it can be reused. The other input and the output, accessed row-wise, do get the full $L$-fold reuse per line. The column-strided term dominates:

$M_{naive} \approx n^3 + \frac{n^3}{L} \approx n^3 \qquad (\text{for } L \gg 1)$

Intuition: almost every access to the column-strided matrix costs a fresh cache line, so the miss count tracks the total number of scalar multiply-adds, $n^3$, rather than being divided down by the line size.

Blocked. Total arithmetic work is unchanged, $(n/B)^3$ block-multiplications, each touching three tiles of $B^2$ elements, i.e. $3B^2/L$ cache lines, loaded once per block-multiply and reused $B$ times within it:

$M_{blocked} \approx \left(\frac{n}{B}\right)^3 \cdot \frac{3B^2}{L} = \frac{3n^3}{BL}$

Substituting $B \approx \sqrt{C/3}$ gives $M_{blocked} = O\!\left(\dfrac{n^3}{L\sqrt{C}}\right)$: the miss count now shrinks as the cache gets bigger, which the naive version's misses never do.

Miss-count reduction (not yet a speedup).

$\frac{M_{naive}}{M_{blocked}} \approx \frac{n^3}{3n^3/(BL)} = \frac{BL}{3}$

The predicted reduction in cache misses is on the order of (block size) times (cache-line size), a constant that does not depend on $n$ once $n$ is large.

Worked example
Take a 1 MiB cache holding float32 words: $C = 262{,}144$ words, and a 64-byte line: $L = 16$ words. Solving $B \approx \sqrt{262144/3} \approx 295.6$, round to a practical power-of-two tile, $B = 256$. For $n = 2048$:

$M_{naive} \approx n^3 = 2048^3 = 8{,}589{,}934{,}592 \approx 8.59\times10^9 \text{ misses}$

$M_{blocked} \approx \frac{3n^3}{BL} = \frac{3 \times 8{,}589{,}934{,}592}{256 \times 16} = \frac{25{,}769{,}803{,}776}{4{,}096} = 6{,}291{,}456 \approx 6.29\times10^6 \text{ misses}$

$\frac{M_{naive}}{M_{blocked}} \approx \frac{BL}{3} = \frac{256 \times 16}{3} \approx 1{,}365\times$

Blocking is predicted to cut cache misses by roughly three orders of magnitude for this cache and matrix size.

Converting a miss ratio into a speedup, which is where this model is usually misread. A 1,365x drop in misses is not a 1,365x drop in runtime, because runtime is arithmetic plus stall, and blocking only touches the stall term:

$T \approx T_{\text{compute}} + M \cdot t_{\text{eff}} \quad\Rightarrow\quad \text{speedup} = \frac{T_{\text{compute}} + M_{naive}t_{\text{eff}}}{T_{\text{compute}} + M_{blocked}t_{\text{eff}}} \;<\; \frac{T_{naive}}{T_{\text{compute}}}$

The speedup is therefore capped by the fraction of naive runtime that was stall in the first place. If the naive version spends 90% of its time stalled, removing every last stall buys at most 10x, no matter how large $BL/3$ is, because $n^3$ multiply-adds still have to issue. That arithmetic floor is concrete here: $2048^3 = 8.59\times10^9$ multiply-adds, which at roughly one per cycle on a few-GHz core is on the order of two to three seconds of pure arithmetic that no amount of tiling removes.

A single measurement makes the size of the gap obvious. Compiling both loop orders in C with clang -O2 and vectorization disabled (so the comparison is about memory, not SIMD) and running $n = 2048$ float32 on one arm64 laptop gave 12.68 s for naive ijk against 2.82 s for the blocked version with $B = 128$, both producing identical output checksums: a 4.5x speedup, about 300 times smaller than the miss-count ratio predicts. The blocked time also lands right at the arithmetic floor estimated above, which is the tell that blocking has already recovered nearly all of the available stall and further memory tuning has almost nothing left to take.

The same measurement also shows the miss model is an upper bound on line requests, not a count of DRAM round trips: $12.68\text{s} / 8.59\times10^9 = 1.5$ ns per predicted miss, while a real DRAM access is tens of nanoseconds, so at most a few percent of the predicted misses can have been full memory round trips. The rest were served by L2 or L3, or overlapped with each other by the out-of-order engine and the prefetcher. Use $BL/3$ to decide whether to block at all and how to pick $B$; use a measurement to claim a speedup.

Trade-offs & pitfalls
This model assumes $n$ is large enough that even one row of the strided matrix cannot survive in cache across the outer loop; for small matrices that already fit entirely in cache, naive and blocked converge and blocking only adds loop overhead. Choosing $B$ too large (violating $3B^2 \le C$ once other live data, such as prefetch buffers, is accounted for) can make blocked worse than naive by causing the tiles themselves to thrash. The model also assumes one cache level; a real tuner derives a block size per level (L1, L2, sometimes L3), which is exactly what tuned BLAS libraries do instead of picking one block size analytically. One more reason the analytic ratio overstates the win: simply reordering the naive loops from ijk to ikj, with no tiling at all, already makes the inner loop stride-1 in both the second input and the output, and captures a large share of the benefit, so the honest baseline for "what did blocking buy me" is the best simple loop order, not the worst one.

Direct answer

Removing malloc/free overhead and GC (garbage collection) pauses from a hot path means
replacing per-request dynamic allocation with memory that is acquired once, ahead of
time, and reused: pooling, arenas, stack allocation, and zero-copy handling of incoming
data. Which mechanism is idiomatic differs across Rust, Go, and C++ because each
language's ownership and memory model changes what "reuse this memory safely" costs to
express.

Structured elaboration

Pooling: pre-allocate a fixed set of reusable objects (or buffers) once at startup,
and hand them out and take them back on the hot path instead of calling the allocator
per request. This trades a small amount of memory held in reserve for eliminating
allocator calls entirely from the latency-sensitive path.

Arenas (bump allocators): allocate one large block up front and satisfy individual
requests by simply advancing a pointer within it; freeing happens all at once (resetting
the arena) rather than per object. This is extremely cheap per allocation (just a
pointer bump) at the cost of not being able to free individual objects early.

Stack allocation: keep short-lived, bounded-size data on the call stack instead of
the heap whenever its size is known at compile time and its lifetime doesn't outlive
the function, since stack allocation is essentially free (a single stack-pointer
adjustment) and requires no bookkeeping to reclaim. Go's compiler makes this decision
for you through escape analysis, a compile-time check for whether a value's lifetime
could outlive the function that created it: if it provably can't, the compiler places
the value on the stack instead of the heap, and go build -gcflags=-m prints the
per-allocation verdict (&Node{...} does not escape versus &Node{...} escapes to heap) so you can confirm the decision rather than hope for it. C++ works the opposite
way, and the difference matters on a hot path: storage duration is a source-level
choice the programmer makes (Node n; is automatic storage, new Node is dynamic),
and no C++ compiler promotes a new to the stack via escape analysis. What a C++
compiler may do is elide the allocation outright when the object is provably local and
dead, which the standard explicitly permits for the replaceable global allocation
function; that elision is fragile, and as soon as the pointer reaches a function the
optimizer cannot see through, the operator new/operator delete pair survives in the
emitted code. So in C++ the way to keep a hot-path object off the heap is to give it
automatic storage in the first place (or place it into an arena you already own), not
to rely on the optimizer noticing.

Zero-copy: avoid copying incoming data (a network buffer, a memory-mapped file) into
a new owned structure when it can instead be referenced or parsed in place, since a copy
is both an allocation and a memcpy the hot path doesn't need to pay for.

Language-specific mechanisms:

• Rust: the ownership and borrowing model makes zero-copy the natural default,
  parsing directly into borrowed slices (&[u8]) instead of allocating owned buffers,
  with the compiler statically enforcing that the borrowed data outlives its use. Object
  pools are typically expressed as a Vec of pre-allocated items with manual
  checkout/return, since Rust has no automatic GC to interfere with reuse, and arenas
  are available via crates (bump allocators) that hand back typed references tied to
  the arena's own lifetime.
• Go: sync.Pool provides a built-in, GC-aware object pool specifically designed to
  reduce allocator and garbage-collector pressure for short-lived objects. Be precise
  about when it is emptied, because the usual shorthand is wrong: the collector drains
  a sync.Pool on every GC cycle, not only under memory pressure. An item survives at
  most one cycle (it is moved to a victim cache) and is dropped on the next, so on a
  small, quiet heap a pool can be empty again milliseconds after you filled it; it is a
  best-effort cache, not a guaranteed-capacity pool. The practical consequence is that
  sync.Pool pays off for objects churned many times between collections and pays
  almost nothing for objects checked out roughly once per GC interval. Because Go still
  has a garbage collector underneath everything, reducing allocation rate (not
  eliminating allocation entirely) is usually the realistic, idiomatic goal: fewer,
  larger, reused buffers mean fewer objects for the GC to track and collect.
• C++: full manual control is available: a custom arena or object-pool allocator,
  placement new into pre-allocated storage, and std::pmr (polymorphic memory
  resource) allocators that let standard containers (std::vector, std::string) draw
  from a custom arena instead of the global allocator without changing the container's
  own interface.

Worked example

A request handler needs a small, short-lived buffer per request to build an outgoing
message. Three approaches, same task:

• Naive (all three languages): allocate a new heap buffer per request, use it, let
  it go out of scope; the allocator and (in Go) the garbage collector both do work on
  every single request.
• Pooled (idiomatic per language): Go checks a buffer out of a sync.Pool and
  returns it via defer pool.Put(buf); Rust checks a buffer out of a pre-allocated
  Vec-backed pool and returns it via a guard type whose Drop implementation returns
  it automatically; C++ does the same via a custom pool class whose destructor returns
  the buffer to the pool (RAII: resource acquisition is initialization, the same "return
  it automatically via a destructor/guard" pattern Rust's Drop also expresses).
• Result: the allocator is called once per pool slot at startup instead of once per
  request, and in Go's case, the objects handed out by the pool are exactly the ones the
  GC no longer needs to discover and reclaim on every request.

Trade-offs & pitfalls

Pooling and arenas both trade memory for speed: a pool sized for peak load holds that
memory even during quiet periods, and an arena that is reset infrequently can grow
unbounded if one long-lived allocation is mixed in with short-lived ones. Zero-copy
parsing in Rust in particular ties the parsed data's lifetime to the original buffer's
lifetime, which is exactly what the borrow checker is protecting, but it means the
original buffer cannot be freed or reused until every borrowed reference into it is
done, which can itself become a source of unwanted memory retention if not scoped
carefully. In Go, over-relying on sync.Pool for large objects can backfire: since the
pool is best-effort and can be cleared by the GC at any time, code must not assume a
Get() always returns a previously-pooled object rather than a freshly allocated one.

Direct answer

This function has two parts with different costs. The nested loop computing total is a triangular double loop that runs exactly n(n-1)/2 times regardless of the input values, so it is Theta(n^2), a tight bound, not just an upper bound. The second loop building prefix runs exactly n times with an amortized O(1) append each, so it is Theta(n). Because n^2 dominates n for large n, the whole function is Theta(n^2), with worst case, best case, and average case all equal, since no branch depends on the array's contents.

Structured elaboration

• First loop (for i in range(n): for j in range(i): total += arr[j]): for each i from 0 to n-1, the inner loop runs exactly i times. Total inner iterations = 0+1+2+...+(n-1) = n(n-1)/2, exactly, independent of the array's contents. This is Theta(n^2) rather than just O(n^2) because the lower bound Omega(n^2) also holds: the loop always does this many iterations, never fewer.
• Second loop (for x in arr: s += x; prefix.append(s)): runs exactly n times, and each .append() is amortized O(1) per the question's own stated assumption (backed by CPython's dynamic-array growth strategy), so this pass is Theta(n).
• Combining: Theta(n^2) + Theta(n) = Theta(n^2), since the quadratic term dominates for n greater than 1.
• Space: prefix = [0] * n allocates an n-element list up front, then the loop appends n more values onto it, one per element of arr. Since .append() does not overwrite the existing zeros, it GROWS the list, so the final prefix has 2n elements, not n: n leading zeros followed by n cumulative sums. That is still Theta(n) additional space (the factor of 2 is a constant, absorbed by big-Theta), but it is worth naming explicitly since a candidate skimming the code might assume prefix ends up holding just the n prefix sums.

Worked example

Running the function on arr = [3, 1, 4, 2] (n=4): first loop: i=0 contributes nothing, i=1 adds arr[0]=3, i=2 adds arr[0]+arr[1]=4, i=3 adds arr[0]+arr[1]+arr[2]=8, so total = 3+4+8 = 15. Second loop: s walks 3, 4, 8, 10 as it sums the array, each value appended onto the pre-sized list. Since prefix started as [0, 0, 0, 0], the actual returned value is (15, [0, 0, 0, 0, 3, 4, 8, 10]), an 8-element list, confirming the "prefix ends up 2n long" point above.

Trade-offs and pitfalls

A common mistake is reporting O(n^2) without checking whether it is also Omega(n^2), which is what earns the tighter Theta(n^2) label; here it is, since the loop structure has no early exit and no data dependence. Another common mistake is assuming [0]*n followed by appends produces an n-length prefix-sum array; tracing the code line by line, rather than pattern-matching "this looks like a prefix sum function", is what catches the doubled-length behavior.