Algorithmic Complexity & Code-Level Optimization Questions

"Measure first" means collect real performance data (latency, throughput, resource usage, error rates) before changing code. "Avoid premature optimization" means don’t spend time complicating code or adding complexity for a problem that doesn't materially exist; optimize only where measurements show a real bottleneck or costly scaling risk.

Checklist to decide whether to optimize:

1. Observe: Gather metrics (APM, logs, perf traces, p95/p99 latency, CPU/memory, DB query time, QPS).
2. Verify impact: Reproduce problem in prod-like load or isolate via profiling (CPU/heap/profile, flamegraphs, SQL EXPLAIN).
3. Quantify benefit: Estimate improvement (e.g., reduce p99 from 800ms→200ms) and translate to business metrics (user conversions, SLA compliance, cost savings).
4. Estimate cost: Developer-hours, increased complexity/risk, test and deployment effort, potential maintenance burden.
5. Compare ROI: If (benefit value) > (cost + risk) and aligns with SLAs/roadmap, prioritize; otherwise document and monitor.
6. Choose scope: Start with targeted change or caching, then measure again; prefer incremental, reversible changes.
7. Validate: Deploy behind feature flag, run canary, monitor key metrics, roll back if no gain or new regressions.

Quick heuristics:

• Optimize if it fixes an SLA breach, saves significant infra costs, or unlocks product needs.
• Defer if improvement is marginal, speculative, or would add long-term complexity.

Big-O describes how an algorithm’s running time grows as input size n increases, abstracting away machine-specific constant factors and lower-order terms. For example, O(n) grows linearly, O(n log n) grows superlinearly but much slower than O(n^2) as n→∞.

Mergesort is O(n log n) because it splits the array (log n levels) and does linear work per level; insertion sort is O(n^2) because it may perform ~n comparisons/shifts for each of n items in the worst case. For large n, n log n << n^2 (e.g., for n=1e6, n log2 n ≈ 20e6 vs. n^2 = 1e12), so mergesort typically outperforms insertion sort.

However, constant factors and memory behavior matter: insertion sort has tiny constants, is in-place, and has excellent cache locality. For small arrays (commonly n ≤ 20–50), insertion sort often runs faster in practice. That’s why hybrid sorts (e.g., Timsort, mergesort with insertion sort for small runs) are common.

To validate empirically in production:

• Benchmark realistic workloads (representative input distributions) using production-like hardware.
• Measure wall-clock time, CPU, memory, and cache/memory allocation impact.
• Run A/B or canary tests with telemetry (latency percentiles, error rates).
• Use profiling to confirm hotspots and verify asymptotic behavior as n scales.
• If results differ from theory, inspect constants, memory allocation, and branch prediction effects before changing algorithms.

Requirements & assumptions:

• Computation: 1e9 CPU cycles.
• Energy per cycle: 3e-11 J/cycle (given).
• Battery: 3000 mAh at 3.7 V.
• Assume all CPU energy comes from battery (ignore other losses, regulator inefficiency, screen, radios).
• 1 mAh = 3.7 mA·h → convert to joules via capacity × voltage × 3600 s/h.

Calculations:

1. Energy for computation:
   E_compute = cycles × energy_per_cycle
   = 1e9 × 3e-11 J
   = 3e-2 J = 0.03 J

2. Battery total energy:
   Capacity = 3000 mAh = 3 Ah
   Energy_batt = V × Ah × 3600 s/h
   = 3.7 V × 3 Ah × 3600 s
   = 3.7 × 10800
   = 39960 J ≈ 4.0e4 J

3. Fraction of battery used:
   fraction = E_compute / Energy_batt
   = 0.03 / 39960 ≈ 7.5e-7

   Percentage = fraction × 100% ≈ 7.5e-5% ≈ 0.000075%

Interpretation and notes:

• The computation uses ~0.03 J, consuming ~0.000075% of the battery — essentially negligible.
• Real-world caveats: CPU energy-per-cycle varies by instruction mix, DVFS state, and peripheral wakeups; power overhead for waking CPU, memory access, and OS scheduling can add energy. If the system must wake from low-power state, the fixed wake/sleep cost (tens to hundreds of mJ) could dominate.
• Example: if wake cost = 50 mJ (0.05 J), that alone is ~0.000125% of battery — still tiny but larger than the cycle cost.

Spatial locality: programs tend to access memory addresses near each other in short time (e.g., sequential array traversal). Temporal locality: recently accessed locations are likely to be accessed again soon (e.g., reuse inside a loop). Caches exploit both by loading contiguous bytes (cache lines) and keeping hot data.

Concrete examples (C-like, row-major double matrix):

Cache-friendly (row-major traversal):

// Iterate rows then columns: contiguous access
for (int i = 0; i < N; ++i)
  for (int j = 0; j < N; ++j)
    sum += A[i][j];

Cache-unfriendly (column-major access on row-major layout):

// Iterate columns then rows: large stride between accesses
for (int j = 0; j < N; ++j)
  for (int i = 0; i < N; ++i)
    sum += A[i][j];

Why locality matters (quantified):

• Typical cache line = 64 bytes. double = 8 bytes → 8 doubles per line.
• For N=1024 (1M elements): row-wise traversal loads ~ (N*N)/8 ≈ 131,072 cache lines (mostly hits after first access per line).
• Column-wise traversal (stride = N*8 = 8192 bytes) causes nearly one miss per access → ~1,048,576 misses.
• That’s ~8× more cache misses; with L1 miss penalty ~10s of cycles and L3/main memory hundreds of cycles, runtime can be orders of magnitude slower.

Takeaway: write loops to access memory contiguously and reuse data when possible (blocking/tiling for matrix ops) to leverage spatial and temporal locality.

Brotli vs gzip — concise comparison and recommendations.

Key differences

• Compression ratio: Brotli (especially at higher levels) typically compresses 10–25% smaller than gzip for text/HTML/CSS/JS. For small JSON/HTML fragments Brotli gains are often meaningful; for already-minified or binary data gains are smaller.
• CPU cost: Brotli (levels >4–6) is significantly more CPU-intensive to compress than gzip. Decompression CPU is modest for both; Brotli decompression cost is slightly higher but typically negligible on modern clients.
• Latency (TTFB/body): gzip at moderate levels (e.g., -6) yields low compression latency and fast first-byte; Brotli at low/medium levels (e.g., 1–4) approaches gzip’s latency while giving better ratios. High Brotli levels increase time-to-first-byte and total time-to-complete on server-side compress before sending.

Use cases

• Static assets (build-time): Use Brotli at high compression (e.g., brotli -11) produced at build time and served precompressed. No runtime CPU cost, best size reductions for CSS/JS/HTML.
• Dynamic API payloads (runtime): Prefer gzip at a moderate level (gzip -5 or -6) or Brotli at low level (Brotli -1 to -3) if server can handle CPU and clients support it. For very latency-sensitive APIs or high QPS, stick to gzip to limit CPU and TTFB.
• Small payloads (<1–2 KB): Compression overhead may not justify cost; consider no compression or use “gzip if large” threshold.

Default compression levels (practical defaults)

• Static build assets: Brotli level 11 for precompression; also keep gzip -6 fallback for older clients.
• Runtime/dynamic responses: gzip level 5–6 (good balance of CPU vs ratio) OR Brotli level 3 if server-side CPU and client support are sufficient.

Justification

• Precompressed Brotli gives best size without runtime cost.
• gzip -5/-6 yields predictable low-latency CPU cost suitable for high-throughput services.
• Brotli low levels trade small extra CPU for better ratio; useful if bandwidth is scarce and latency budget allows.

Operational notes

• Respect Accept-Encoding and user-agent capabilities; serve precompressed files when present with correct Content-Encoding and Vary headers.
• Benchmark with representative payloads and measure TTFB, CPU, and bandwidth, then tune thresholds and worker counts accordingly.