Big-O Notation

Big-O ignores constants and keeps the dominant term:

Big-O	Name	Example
$O(1)$	constant	array index, hash lookup
$O(\log n)$	logarithmic	binary search
$O(n)$	linear	scanning a list
$O(n \log n)$	linearithmic	merge sort
$O(n^2)$	quadratic	nested loops, bubble sort
$O(2^n)$	exponential	brute-force subsets

For $n = 10^6$, $O(n \log n)$ is about $2 \times 10^7$ steps, while $O(n^2)$ is $10^{12}$ — the difference between milliseconds and hours.