Big-O is easy to calculate, if you know how
This is the second in a three post series. The first post explains Big-O from a self-taught programmer's perspective. The third article talks about understanding the formal definition of Big-O.
So now that we know what Big-O is, how do we calculate the Big-O classification of a given function? It's just as easy as following along with your code and counting along the way.
def count_ones(a_list): total = 0 for element in a_list: if element == 1: total += 1 return total
The above code is a classic example of an
O(n) function. This is
because we have to loop over every element that we get in order to
complete our calculation. We can trace this by following along the
code and counting. We're doing a few calculations here.
- We're setting
- We loop through
- We check if
elementis equal to 1.
- We increment
totalby one a few times.
So setting a counter to zero is a constant time operation. If you
think about what's happening inside the computer, we're setting a
chunk of memory to some new value. Because we've hard-coded the zero
here, it happens in constant time. There's no way to call this
function or alter global state that we could change the
operation. This is an
Next, we loop through the list. So we have to look at each item in the
list. This number of operations changes depending on the size of the
list. If it's a list of 10 things, we do it 10 times. If it's 75, we do
75 operations. In mathematical terms, this means that the time it
takes to do something increases linearly with its input. We use a
variable to represent the size of the input, which everyone in the
n. So the "loop over the list" function is
n represents the size of
Checking whether an element is equal to 1 is an
O(1) operation. A
way to prove to ourselves that this is true is to think about it as a
function. If we had an
is_equal_to_one() function, would it take
longer if you passed in more values (eg
is_equal_to_one([1,2,3,4,5])? It wouldn't because of the fixed
number 1 in our comparison. It took me a while of conferring with
other people about why this was true before I was convinced. We
decided that binary comparisons are constant time and that's what a
comparison to 1 eventually got to.
Next, we increment total by 1. This is like setting total to zero (but you have to do addition first). Addition of one, like equality, is also constant time.
So where are we? We have \(O(1) + O(n) * (O(1) + O(1))\). This is because we do 1 up front, constant time operation, then (potentially) 2 more constant item things for each item in the list. In math terms, that reduces to \(O(2n) + O(1)\). In big O, we only care about the biggest "term" here. "Term" is the mathematical word that means "portion of an algebraic statement".
To figure out the biggest expression if you don't remember the order,
you can just cheat and graph them. From the other article, we know
that to graph these things you just replace
So as I was saying, in calculating Big-O, we're only interested in the
O(2n). Because Big-O only deals in approximation, we
drop the 2 entirely, because the difference between
fundamentally different. The growth is still linear, it's just a
faster growing linear function. You drop the products of (aka things
multiplying) the variables. This is because these change the rate of
growth, but not the type of growth. If you want a visual indication
of this, compare the graph of
x^2 is a
different type of growth from the other two (quadratic [which is
just a math-y way of saying "squared"] vs linear), just like
2n is a
different type of growth from
1 in the graph above (linear vs
constant). Even if you pick a really high multiplier like 10,000, we
can still beat it with
x^2 because eventually the line for
be higher if we go far enough to the right.
To sum it up, the answer is this function has an
O(N) runtime (or a
linear runtime). It runs slower the more things you give it, but that
should grow at a predictable rate.
The key aspects to determining the Big-O of a function is really just as simple as counting. Enumerate the different operations your code does (be careful to understand what happens when you call out into another function!), then determine how they relate to your inputs. From there, its just simplifying to the biggest term and dropping the multipliers.
If you found this interesting, I'm thinking about writing up a longer form book on this topic. Head over to leanpub and express your interest in hearing more. If you have any questions, please feel free to email me.