Original subtitles

In this clip, we will talk about asymptotic performance, which means not only to consider an expression or

a curve that describes how execution time evolves for an algorithm, but also to only consider the significant

paths of that expression, that is, the parts that constitutes the majority of the execution time.

Consider this simple ccr function that initializes a calendar and keeps incrementing it with 1 and writing

out its value until it reaches an upper limit, N. We can now ask, how complex is this function or algorithm?

Let's count instructions. The initialization takes one instruction, the comparison inside the while

condition also takes one instruction. For simplicity, we assume that the Console.WriteLine also consumes one

instruction, and that the increment and assignment consumes one each, too.

The loop is repeated N times, and the resulting expression can be shortened like this.

If we draw that expression as a curve, it looks like this, a straight line.

Take a look at this underlined 1. When N grows, that becomes quite insignificant.

Also assume that our program was run on an iPhone and that the curve represents the execution time there.

If we took the exact same function and ran it on the much faster laptop, the curve may have looked like this,

still a straight line, but with a smaller slope. If we, for the sake of simplicity, say that the laptop is

exactly twice as fast as the iPhone, which is an understatement to say the least, then the formula for the

line would be 0.5 + 2N. So the number 4 we got when counting instructions can be considered scaled up and

down, depending on which hardware that runs the code. And we can therefore ask if that constant helps

understanding the nature of the performance behavior.

So, it seems that the significant part of the expression for the execution time in this example is N times

some constant factor where this constant factor depends on a number of things.

For example, which hardware that runs the code. Let's consider a slightly more complex example with a

function that iterates over all integer pairs for integers between 0 and N.

Recognize the inner loop from the previous example. We already calculated the complexity of that.

Also notice that the other loop is actually similar to the inner loop, and thus we also have an expression

for the complexity of that. The only difference is that instead of calling Console.WriteLine, we execute the inner loop.

Last we have a couple of initializations. Let's construct this a bit.

1 + 1 = 2, 1 + 1 + 2 = 4, and 1 + 2 = 3. Let me remove all of these spaces, and multiply the N outside the

parentheses with the 3 and 4N from inside the parentheses.

If we draw this expression, the curve looks like this. Again, if that curve represents the execution time

on the iPhone, and we also executed a similar function on the laptop, we get an expression like this.

Again, we have the simplified assumption that the execution time is only cut in half on the laptop,

but notice that the nature of the curve does not change when executing the program on a faster or slower machine.

It only gets scaled by a constant factor, up or down. We can see, however, that whereas the previous example

had a linear execution time, the execution time in this example is clearly dominated by the factor N squared.

The takeaway from these two examples is that the constant factors may be overruled anyway by a change of

execution hardware, so they may be omitted and we will still be able to get the interesting information about

how the execution time grows with the input size. That is, when doing asymptotic performance analysis,

we can ignore constant factors. And also as we shall see in a moment, we can actually focus on only the

component in the instruction count expression with the highest order.

In this example, the highest order component is N squared.