Big O describes how the work grows with the input. Halving each step is O(log n); comparing every pair is O(n²).
The card game
You want a card in a sorted deck. Checking from the top is O(n). Cutting the deck in half each time is O(log n). Comparing every card with every other is O(n²).
The numbers
Items
O(log n)
O(n²)
52
6
2,704
1,000
10
1,000,000
At 52 cards, both feel fine. At 1,000 the difference is enormous.
The common mistake
Try it: two nested loops over the same list of n items. What is the Big O? Answer: O(n²).
AI explanations can contain mistakes. Check important answers with your teacher.
AI explanations can contain mistakes. Check important answers with your teacher.
