Complexity and efficiency basics

Big-O notation describes how an algorithm's run time scales with input size $n$.

Common complexity classes

How to determine complexity

• A single for loop over $n$ items → $O(n)$.
• A nested for loop (both over $n$) → $O(n^{2})$.
• Halving the problem each step → $O(\log n)$.

Space complexity measures memory usage by the same logic.

Practical example — Computing all pairwise distances between $n$ particles:

# O(n^{2}) — unavoidable for all-pairs
for i in range(n):
    for j in range(i + 1, n):
        dist = np.linalg.norm(pos[i] - pos[j])

For large $n$, algorithms like Barnes-Hut ($O(n\log n)$) use spatial trees to approximate distant interactions.

Physics link: Molecular dynamics with $N$ particles requires $O(N^{2})$ force evaluations per time step. Reducing this to $O(N\log N)$ via fast multipole methods enabled simulations of millions of atoms.

Common pitfall: Big-O hides constants: an $O(n^2)$ method can beat an $O(n\log n)$ one on small inputs. Complexity classes predict scaling, not which code wins today’s benchmark.