Big O notation

Big O keeps only the dominant growth term and drops constant factors — how cost scales as $n$ gets large.

Big O

$T(n)\in O(f(n))$ if there exist constants $c$ and $n_0$ such that $T(n) < c\cdot f(n)$ for all $n > n_0$. We say $f(n)$ is an asymptotic upper bound.

As n grows, exponential cost explodes far faster than linear or quadratic.

Drop lower terms

$T(n)=2n^2+10n+50$. For large $n$, the $n^2$ term dominates. Indeed $T(n)<6n^2$ for $n>5$, so $T(n)\in O(n^2)$.

Checking all pairs for duplicates

Nested loops over unique pairs compare $n(n-1)/2$ pairs in the worst case → $T(n)=\tfrac{{1}}{{2}}n^2-\tfrac{{1}}{{2}}n\in O(n^2)$.

Key takeaways

Keep the fastest-growing term.
Ignore constant multipliers.
Linear scan $O(n)$; all-pairs $O(n^2)$.