Big-O and Choosing a Structure

Big-O describes how the work grows as the input grows — it is how you compare structures and algorithms. The ones you meet most:

• O(1) constant — the same work whatever the size (array index, hash map lookup)
• O(log n) logarithmic — halves the problem each step (binary search in a sorted array)
• O(n) linear — work grows with the size (scanning a list)
• O(n²) quadratic — a loop inside a loop; slow as data grows

See the difference. Binary search halves the range each step, so it finds an item in a big sorted array in very few checks: