What is complexity analysis, and why do computer scientists use it?
Production-level computer programs – the kind used by companies like Google and Facebook – are very large and incredibly complex. They have hundreds of thousands of lines of code. So how can they ensure that things are running as fast as they can be?
Of course, there are tools for this. Profilers are basically complicated programs that go through other programs and calculate how much time is being spent and where. Using this, a human can go through and try to figure out where to make things faster.
But do you think this is how companies do it? They write garbage the first time, throw it at the profiler, which then tells them that it is garbage, and then they resolve to fix it later?
Of course not. They want the first draft to be as close as possible to the final shipment!
So how can we get a really good first-order approximation for a fast program?
Enter complexity analysis.
Complexity analysis gives us a good way of choosing the algorithm that will be the fastest for various given input sizes. When done correctly, it guarantees that no other algorithm is faster. Of course, your program may still be slow because of implementation issues, but fixing implementation issues is far closer than changing the algorithm itself!
1. Constants don’t matter
They don’t. Not for complexity analysis.
Imagine you had an algorithm that evaluated to
O(n^2 + 5). Is that really so different than
O(n^2 + 8)? No.
Let me play devil’s advocate for a moment. Why isn’t it different? The first algorithm is, by definition, faster than the second. Shouldn’t it be preferred?
Remember the purpose of complexity analysis: To give a good first order approximation. The constants
8 can be sorted out during the implementation details. A particularly clever implementation might actually get rid of that constant entirely, who knows.
The important thing here is that the relationship between the input size and the algorithm complexity is
2. Choose the driving term
Think of these complexity factors as a function. Which term drives the function?
O(n^3 + n^2 + n + 1), it’s obvious that the
n^3 is the major determining factor of the result. That’s the most important thing, and, as
n gets larger, it drowns out the other two terms.
It is for this precise reason we say that
O(n^3 + n^2 + 1) evaluates to
You may have noticed many sorting algorithms use
O(n•log(n)), and thus are wondering why don’t we just evaluate that to
n is clearly larger than
log(n). The difference is that
n•log(n) is a single term due to the multiplication, whereas the addition of
n^3 + n^2 shows they are two separate terms. We cannot reduce a single term further.
3. Big Oh
What does the capital O (called “Big-Oh”) really mean? Computer scientists don’t just put it there for good times. It turns out there is a specific meaning associated with it, and there are other Big letters that we won’t go over in this class.
Big-Oh sets an upper bound. That is, it means that this is the most this code can be. This means that, technically, even a code that is
O(n) is indeed
O(n^2) or even
O(n^3), because indeed a code that is linear will never go beyond a cubic function.
So why don’t we just say
O(n^10000) for every single question and be done with it? Because it’s not precise. We’re after the most correct answer, which is the estimation that most closely approximates the code.
This means that even though
O(n^5) is technically correct, if the code is actually
O(n^2), you will lose points on exams for writing the former answer.
One last point is that when discussing complexity, we need to know what
n is. So whatever code is presented, you should provide some context.
No point in just sitting around discussing theory though. Let’s do tangible examples. Don’t just look at the answer though, take a moment to figure it out yourself.
a = *100 for elem in a: for elem2 in a: print str(elem2) + str(elem1)
What’s the time complexity of just the first loop? It must be
O(n) because the for loop goes over every element in
a once. Okay, what about the second loop? This one is also
O(n) for the same reason.
Since the loops are nested, the total runtime must be
O(n) • O(n), which is
Thus, this code is
n is the length of the list
n = 1048 while n > 0: print n n = n / 2
This one is slightly tricky. Think about (really) before giving up.
At first you might be tempted to think it’s
O(n) because, as we said above, constants don’t really matter. But dividing
2 every time is not a constant. It’s actually a separate term that can be expressed as a math function.
This code is
n is the variable in the code
You might be wondering why I didn’t tell you what base it was. Those of you who remember your maths might be remembering that you can actually convert from any base to any other base with a simple constant term, and that’s exactly right.
Because we can convert from bases with a simple constant, and constants don’t matter, it doesn’t matter what base you mean when you say the “logarithm of n”. In this case, it would be log base
2, but of course that’s irrelevant.
Logs are quite common in run-times, so I’d get used to recognizing them!
m = 1000 i = 0 while i < m: for j in range(i): print j i += 2
No matter how complex the code, start basic.
What’s the complexity for the
while loop? It goes over half the numbers from
i is incremented by
2 every loop iteration. So that’s
n is the variable
m. But as we know, constants don’t matter. So that’s simply
Great. What about the inner
for loop? This one seems to be a little tricker. Remember that Big-Oh notation sets an upper bound. What’s the maximum that
i can be?
m. Right. Which means in the worst case, the largest case, the most time the
for loop can take is
Thus, the runtime of this whole code block is
n is the variable
Another way to think about this is using arithmetic series. Remember that short assignment where you had to calculate the sum of
n and you had a formula that was
n • (n + 1) / 2? Well, the Big-Oh of this formula is
What’s happening here is quite similar to an arithmetic series, only we’re incrementing by
2 instead of by
1 every time. But that doesn’t change the Big-Oh, since we’re not concerned with constants.
The following images are from Lode Vandevenne’s website.
We’re going to estimate the runtime of an algorithm called the Sierpinsky Carpet. We start with a single square of length
Draw a square in the middle where the size of each side is
Now around the black square are eight white squares of equal sizes. Draw black squares inside each of these eight white squares where the side of these new black squares are one third the size of the white squares. Thus, the new black squares’ sides are of length
Keep going, until the sizes of any square are just a single pixel.
And so on, and so forth.
Express your answer in terms of
w. (This one’s a toughie!)