Complexity and Core Data Structures

Your system receives 1 million orders a day, and someone proposes comparing every order with every other one to find duplicates. Is that fine? Big-O notation answers this before you write any code. It describes how the number of basic operations grows with the input size $n$, dropping constants and lower-order terms, so $3n^2 + 50n + 7$ is $O(n^2)$.

Formally, $f(n) = O(g(n))$ means $f(n) \le c\,g(n)$ for some constant $c$ once $n$ is large enough. That is an upper bound. $\Omega$ is the matching lower bound, and $\Theta$ means both hold, so the growth rate is pinned exactly. In interviews people say "big-O" when they mean $\Theta$, and that is usually fine.

The classes you will meet, from fast to slow, are $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$ and $O(2^n)$. With $n = 10^6$:

Even at $10^8$ simple operations per second (compiled code; plain Python is closer to $10^7$), the all-pairs check takes $10^4$ seconds, close to three hours. Sorting by order ID and comparing neighbours is $O(n \log n)$ and finishes in well under a second.

To find the complexity, count loops. One pass over the data is $O(n)$. A loop inside a loop over the same data is $O(n^2)$. Halving the problem at each step, as binary search does, gives $O(\log n)$, because you can halve $n$ only about $\log_2 n$ times. Also state the space complexity, the extra memory an algorithm uses, since most of the tricks below spend memory to save time.