Glossary

Algorithm Complexity (Big O)

Big O notation is a way to describe how the execution time or memory usage of an algorithm grows with input size n. It lets you compare algorithms independently of hardware.

Common classes

O(1) — constant time. Array index access, hash table lookup. Does not depend on n
O(log n) — logarithmic. Binary search. Fast even for billions of elements
O(n) — linear. Array traversal. Double n → double time
O(n log n) — Merge Sort, QuickSort (average case)
O(n²) — nested loops. Bubble Sort. Impractical for n > 10,000
O(2ⁿ) — exponential. Enumerating all subsets. Far too slow

In practice

A SQL query without an index is O(n). With an index it is O(log n). That is why indexes matter 100× more than optimising application code.