Before any data structure, learn to measure cost. Big-O describes how an algorithm scales with input size, independent of hardware — the language you use to compare solutions and the reason the rest of DSA matters.
Timing code in seconds depends on your machine, language, and load — useless for comparing algorithms. Big-O instead describes how the number of operations grows as the input grows, which is a property of the algorithm itself. It lets you say "this approach is fundamentally faster" before writing a line, and it is the vocabulary all of DSA is spoken in.
Two ways to measure an algorithm:
seconds depends on CPU, language, other load -> not comparable
Big-O how operations GROW as input n grows -> a property of the
algorithm, machine-independent
Example: search a list of n items
linear scan ~n operations -> O(n)
binary search ~log2(n) operations -> O(log n)
For n = 1,000,000: linear ~1,000,000 steps ; binary ~20 steps.
Big-O tells you that BEFORE you run anything. That's why we learn it first.Big-O expresses an upper bound on growth, conventionally the worst case. Two rules make it usable: drop constant factors (2n and n both scale linearly, so both are O(n)), and keep only the fastest-growing term (n² + n is O(n²) because n² dominates as n grows). You are describing the shape of growth, not an exact operation count.
Big-O = an upper bound on how cost grows (usually worst case).
Two simplification rules:
1. drop constants: 5n + 3 -> O(n) 2n -> O(n)
2. keep the dominant term: n^2 + n + 100 -> O(n^2)
(as n grows, n^2 dwarfs everything else)
So we care about the SHAPE of growth, not exact counts:
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)
<-------------------- faster slower -------------------->A handful of complexity classes cover almost everything you will meet. Recognizing them on sight — a single loop is O(n), a nested loop is O(n²), halving each step is O(log n) — is the core skill. The dangerous ones are exponential O(2ⁿ) and factorial O(n!): they are fine for tiny inputs and hopeless beyond ~20–40 elements.
# O(1) constant — one operation regardless of n
def first(a): return a[0]
# O(n) linear — one pass
def total(a):
s = 0
for x in a: s += x # n iterations
return s
# O(n^2) quadratic — nested loop over the same input
def has_dup_pair(a):
for i in range(len(a)):
for j in range(i+1, len(a)): # n * n / 2 -> O(n^2)
if a[i] == a[j]: return True
return False
# O(log n) — the search space halves each step (see binary search later)
def count_halvings(n):
steps = 0
while n > 1:
n //= 2 # halve -> log2(n) iterations
steps += 1
return stepsBig-O applies to memory as well as time. Space complexity counts the extra memory an algorithm uses as input grows — a running sum is O(1) space, but building a hash set of all elements is O(n) space. Much of algorithm design is a time-space trade-off: you spend memory (a hash map) to save time, or vice versa. Always consider both.
# O(n) TIME, O(1) SPACE — reuse one accumulator
def total(a):
s = 0 # constant extra memory
for x in a: s += x
return s
# O(n) TIME, O(n) SPACE — build a set as big as the input
def uniques(a):
seen = set() # grows with n
for x in a: seen.add(x)
return seen
# the classic trade-off: spend O(n) SPACE (a hash map) to cut a problem
# from O(n^2) TIME down to O(n). You'll do this constantly (next lesson).To find an algorithm’s Big-O, count how the work scales with the loops and recursion over the input. Sequential steps add (and you keep the biggest); nested loops multiply; halving the input each step gives a log factor. With practice this becomes instant pattern recognition, which is exactly what interviews and real performance work require.
A recipe for reading Big-O off code:
a single loop over n -> O(n)
two SEQUENTIAL loops -> O(n) + O(n) = O(n) (add, keep biggest)
a loop NESTED in a loop -> O(n) * O(n) = O(n^2) (multiply)
input halves each iteration -> O(log n)
loop that does O(log n) work -> O(n log n) (e.g. good sorts)
recursion: (work per call) * (number of calls)
Ask: "as n doubles, how does the number of operations change?"
same -> O(1) ; doubles -> O(n) ; quadruples -> O(n^2) ; +1 step -> O(log n)