n is the input size
an algorithm is a set of steps for solving a problem.
n could count names, table rows, or characters in a message.
always say what n measures.
an interactive field guide
how does the work grow?
big O shows how work grows as an input gets bigger.
let's make that feel obvious.
01 / feel the difference
one input.
many futures.
imagine n is the number of items. drag the slider to see the work grow.
these are simple examples, not exact running times.
growth lab
what if n = ?
one “step” means one unit of work in our model.
1100
input size: 1100
vertical scale is logarithmic: each horizontal line is 100 times the work of the one below it.
O describes a bound
it describes how quickly work can grow as n gets large.
it doesn't tell you the exact time a program takes.
focus on the shape
ignore constants and smaller terms: 3n + 8 is O(n).
for small inputs, those details can still matter.
02 / try it yourself
find one number.
two ways.
linear search checks one item at a time.
binary search uses a sorted list. each check rules out half the remaining items.
sorted list / 16 items
0 comparisons
03 / read the code
count the work.
see the pattern.
pick a snippet and change n to see how many checks it makes.
each example is small enough to inspect.
pseudocode
number of checks
8bounds, clearly
big O, Ω and Θ
O is an upper bound. Ω (omega) is a lower bound.
Θ (theta) is both: a tight growth bound.
people often say “big O” when they mean the tight worst-case bound.
which case?
best, average, worst
linear search finds the first item in one check: O(1) best case.
its worst case checks every item: O(n).
the average case depends on assumptions about the input.
memory matters too
space complexity
space complexity describes how memory use grows with input.
one counter uses O(1) extra space. copying n items uses O(n).
input storage may be counted separately.
read the details
two inputs, two names
compare each of n items with each of m items: O(nm).
don't call it O(n²) unless n and m grow together.
04 / the field guide
put the names
to work.
these are common examples.
the algorithm, data structure and case all matter.
constant
access an array element by index.
the work stays constant as the array grows.
logarithmic
binary search on sorted data repeatedly discards half the remaining choices.
linear
scan an unsorted list for a value. worst case: check every item.
linearithmic
merge sort divides the list into levels, then merges n items across those levels.
quadratic
compare every item with every other item.
insertion sort is O(n²) in the worst case.
exponential
enumerate every subset of n items: every item can be included or left out.
!
big O isn't a stopwatch. O(n) can beat O(log n) for small inputs.
constants, hardware, allocation and data access also matter.
measure real code as well.
05 / go deeper
the details
that change the answer.
open a question when you're ready.
these ideas help you apply the notation beyond the first examples.
what does the O bound mean mathematically?
let T(n) be the work for the case you're describing.
T(n) is O(f(n)) if positive constants c and n₀ exist such that T(n) ≤ c × f(n) for every n ≥ n₀.
O is an upper bound. a linear algorithm is also O(n²), but O(n) is tighter.
why doesn't the base of the logarithm matter?
changing a logarithm's base multiplies it by a constant.
we ignore constant multipliers, so O(log₂ n) and O(log₁₀ n) describe the same growth class.
what is amortized complexity?
amortized complexity averages work across a sequence of operations, not random inputs.
an expanding array sometimes copies its contents when it grows.
with the usual doubling strategy, n appends cost O(n) total: O(1) amortized per append.
do data structures and sorting always have one cost?
no. a hash lookup is often expected O(1) under suitable hashing assumptions, but can be O(n) in the worst case.
merge sort takes O(n log n) time and commonly uses O(n) extra space.
quicksort is typically O(n log n) on average, but O(n²) in the worst case.
what about recursion and graphs?
count the work of each call and how many calls occur.
recursive calls use stack space: a chain of n calls uses O(n).
graph traversal with an adjacency list takes O(V + E): vertices plus edges.
06 / make it stick
your turn.
think it through.
choose an answer and see the reasoning.
a wrong answer is useful too.
quick practice
the idea to keep
when the input grows,
what grows with it?
that question is your starting point.
count the work, name the input, and say which case you're describing.
explore again