Two algorithms can both be correct, but one may do much more work. Big O is a simple way to talk about how that work grows.
We do not care about one tiny race. We ask what happens when 10 items become 1,000 items, or one million items.
O(1): one quick step
Reading one array item by its index is O(1). The array may hold ten boxes or a million boxes. If we know the address, we still jump to one box.
O(n): check the whole line
Linear search is O(n). If the list becomes twice as long, we may need about twice as many checks. The letter n means the number of items.
O(log n): cut the problem in half
Binary search is O(log n). Each step throws away half of a sorted list. A list can grow a lot while the number of extra checks grows only a little.
O(n²): every item meets every item
If we use one loop inside another loop, the work can be O(n²). Ten items might make about 100 pairs. One hundred items might make about 10,000 pairs. This grows quickly.
- O(1) stays almost flat.
- O(log n) grows very slowly.
- O(n) grows with the list.
- O(n²) grows much faster.
Big O does not tell us the exact seconds. It gives us the shape of growth. A simple algorithm can still be best for a small job, so we use Big O as a guide, not a strict winner medal.
def first_item(items): # O(1)
return items[0]
def find_red(items): # O(n)
for item in items:
if item == "red":
return True
return False
colors = ["blue", "yellow", "red"]
print(first_item(colors))
print(find_red(colors))Your tiny challenge
Imagine a class with five children. First, give one sticker to the first child. Then give one sticker to every child. Finally, make every child high-five every other child. Which jobs look like O(1), O(n), and O(n²)?