BeginnerHabits & complexity
What Big O actually measures
Big O isn't seconds: it's how the work grows as the input grows. Double n and see what happens to the steps.
The idea
Big O describes how the number of steps grows when the input gets bigger. It ignores the exact speed of your computer and small constant costs, and asks one question: if n doubles, what happens to the work?
O(n) means the work grows in step with n: double the input, double the work. O(n²) means double the input, four times the work, because you usually have a loop inside a loop. O(1) means the work doesn't grow at all.
Worked example
Counting steps for two ways to find a duplicate in [3, 1, 4, 1]
- Compare every pair: (3,1), (3,4), (3,1), (1,4), (1,1) → found. For n items that's about n²/2 comparisons: O(n²).
- Walk once and remember what you've seen in a set: 3, 1, 4, then 1 is already in the set → found. One pass: O(n).
- With 100,000 numbers, the first way does about 5 billion comparisons, the second about 100,000. That gap is what Big O predicts.
In code (Python)
# O(n^2): every pair
def has_dup_slow(nums):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] == nums[j]:
return True
return False
# O(n): one pass with a set
def has_dup_fast(nums):
seen = set()
for x in nums:
if x in seen:
return True
seen.add(x)
return FalseHow to spot it
- One loop over the input → usually O(n).
- A loop inside a loop over the same input → usually O(n²).
- Halving the problem each step (binary search) → O(log n).
Common mistakes
- Counting a built-in as free: `x in my_list` is O(n), `x in my_set` is O(1).
- Calling a solution O(n) when it sorts first: sorting is O(n log n).
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →