Complexity and efficiency basics

Big-O Notation

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

Space complexity measures memory usage by this exact same logic.

Scaling and Pitfalls

To determine complexity: single loop is $O(n)$, nested loop is $O(n^2)$, and halving the input is $O(\log n)$.

Practical example: Computing pairwise distances between $n$ particles uses nested loops, yielding $O(n^2)$. Advanced methods like Barnes-Hut reduce this to $O(n\log n)$ using spatial trees.

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 micro-benchmarks.