Complexity Analysis

Why Bother

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!

How-To

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 5 and 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 O(n^2).

2. Choose the driving term

Think of these complexity factors as a function. Which term drives the function?

In 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 O(n^3).

You may have noticed many sorting algorithms use O(n•log(n)), and thus are wondering why don’t we just evaluate that to O(n), since 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.

Examples

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.

Puzzle 1

a = [0]*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 O(n^2).

Thus, this code is O(n^2) where n is the length of the list a.

Puzzle 2

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 n by 2 every time is not a constant. It’s actually a separate term that can be expressed as a math function.

This code is O(log(n)) where n is the variable in the code n.

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!

Puzzle 3

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 0 to m because i is incremented by 2 every loop iteration. So that’s O(n/2) where n is the variable m. But as we know, constants don’t matter. So that’s simply O(n).

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 O(n).

Thus, the runtime of this whole code block is O(n^2), where n is the variable m.

Another way to think about this is using arithmetic series. Remember that short assignment where you had to calculate the sum of 1 through n and you had a formula that was n • (n + 1) / 2? Well, the Big-Oh of this formula is n^2, right?

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.

Challenge: Sierpinsky Carpet

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 w.

Draw a square in the middle where the size of each side is w/3.

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 w/9.

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!)