Big O notation is the language we use for talking about how long an algorithm takes to run. It's how we compare the efficiency of different approaches to a problem.
It's like math except it's an awesome, not-boring kind of math where you get to wave your hands through the details and just focus on what's basically happening.
With big O notation we express the runtime in terms of - brace yourself - how quickly it grows relative to the input, as the input gets arbitrarily large.
Let's break that down:
How quickly the runtime grows
It's hard to pin down the exact runtime of an algorithm. It depends on the speed of the processor, what else the computer is running, etc.
So instead of talking about the runtime directly, we use big O notation to talk about how quickly the runtime grows.
Relative to the input
If we were measuring our runtime directly, we could express our speed in seconds.
Since we're measuring how quickly our runtime grows, we need to express our speed in terms of...something else. With Big O notation, we use the size of the input, which we call "n". So we can say things like the runtime grows "on the order of the size of the input" (O(n)) or "on the order of the square of the size of the input" (O(*n^*2)).
As the input gets arbitrarily large
Our algorithm may have steps that seem expensive when n is small but are eclipsed eventually by other steps as n gets huge. For big O analysis, we care most about the stuff that grows fastest as the input grows, because everything else is quickly eclipsed as n gets very large. (If you know what an asymptote is, you might see why "big O analysis" is sometimes called "asymptotic analysis.")
If this seems abstract so far, that's because it is. Let's look at some examples.
def print_first_item(items):
print(items[0])
This function runs in O(1) time (or "constant time") relative to its input.
The input list could be 1 item or 1,000 items, but this function would still just require one "step."
def print_all_items(items):
for item in items:
print(item)
This function runs in O(n) time (or "linear time"), where n is the number of items in the list.
If the list has 10 items, we have to print 10 times. If it has 1,000 items, we have to print 1,000 times.
def print_all_possible_ordered_pairs(items):
for first_item in items:
for second_item in items:
print(first_item, second_item)
Here we're nesting two loops. If our list has n items, our outer loop runs n times and our inner loop runs nn times for each iteration of the outer loop*, giving us n^2 total prints. Thus this function runs in O(n^2) time (or "quadratic time").
If the list has 10 items, we have to print 100 times. If it has 1,000 items, we have to print 1,000,000 times.