Original subtitles

Recall the method from before that just loops through N numbers and writes the current number to the console.

As you might remember, we estimated it to consume 4N + 1 instructions given an input parameter N.

Here I have named that expression f of N and drawn it in the graph to the left for various values of N.

Without any reason, at least for now, I'll introduce another function and name it g of N.

I define g of N as just N. Now, I can come up with a number, say 3, and multiply g of N with that number.

Here is the corresponding graph. And as you can see, the first function, f of N, stays above 3g of N everywhere.

Similarly, I can come up with another number, say, 5, and multiply g of N with that.

Here is the corresponding graph. As you can see, f stays under 5g of N.

So we now have two boundaries for f, a lower bound and an upper bound.

This means that if stays within the gray area, and is squeezed in between the two boundaries.

Notice that the only difference between the upper bound and the lower bound is the constants that g of N is multiplied with.

And therefore, the curve of our real execution complexity, f, is of the same nature as the curve described by g.

This may require some thoughts, but remember that running a given program on slow and fast hardware will

result in the same kind of curve if we draw the execution time for various sizes of input.

The only difference is some constant factor. Thus, if we can bound the real execution time within the two

constant factors of a certain curve, we can use that curve to describe the behavior of the complexity of our program.

In this case, we could use g of N to describe the complexity of f of N.

Another way to write this is to say that f is Big Theta of g of N.

That is, f is Big Theta of N, since g of N was just N. As an example of a curve that is not Big Theta of N,

that is, a curve that cannot be bounded by g of N multiplied with some constant factors, take a look at this curve.

Let's consider another example. Recall this example from before that has two nested loops and produces all

pairs of integers between 0 and N, or N - 1 to be precise.

Let's take a look at some graphs. As you might remember, we calculated the complexity as I have written on

the screen here, and as you can see, this is not a straight line.

Again, I have named the expression f of N. Let's try to see if we can bound that function to like we did before.

I introduced a new function, g of N, which I set to the most significant component in f of N, namely N squared.

Similarly as before, I can use a constant factor, say, 3, and multiply g of N with 3 to obtain a lower bound for f.

Also, I can use the constant factor 5 to obtain an upper bound of f, namely 5g of N.

Here is a graph, and notice that f stays under 5g of N for almost all values of N.

To see why I say almost all, consider this table. The table contains the first four values of N,

and the corresponding values of f of N. Here are the values of 5g of N, and as you can see, 5g of N is

actually smaller than f of N until N is 4. So, 5g of N is only an upper bound after N is strictly larger than 3.

We can now write that f of N is squeezed in between g of N multiplied with a low and a high number

respectively, when N is strictly larger than 3. We had a shorter way to write this, as you remember from

the previous example, namely that f is Big Theta of g of N, and since g of N equals N squared, we can also

write this as Big Theta of N squared. An example of a curve that is not Big Theta of N squared is the line from before.

That line was Big Theta of N and grows much slower, as you can see.

Okay, time to be a bit more explicit about this Big Theta. What is it exactly?

So consider a function f. I have put the function from the previous example up as an example in the gray box.

We then need three things to exist in order for f to be Big Theta of some other function g of N.

First of all, we need some function g of N in the first place, and as you can see, a good candidate for g of

N is the element from f of N with the highest order. In the examples in the gray boxes, it's N squared.

Next, we need two constants. Here I have called them c1 and c2, and in the examples from before,

these have the values 3 and 5, respectively. We also need a third constant, say, small n.

In the example, small n was the constant 3 that capital N had to be strictly larger than before the

boundaries were actually boundaries. So, if f can be squeezed in between c1 times g of N and C2 times g of N,

whenever capital N is strictly larger than small n, then we say that f is Big Theta of g of N,

and typically we just write whatever g of N is. In the previous example, we just wrote Big Theta of N squared.

We use Big Theta to express complexity, but how do we express that something takes constant time, that is,

the same amount of time independently of the input size n? Let's say that a part of a program uses,

for example, 19 instructions independently of n. We can use the same principles as before, so introduce a

function g of N and set it to 1, just the constant 1. Now introduce a constant factor, say, 18.999 and

scale g of N with that. So now I have a lower bound. Also, introduce another constant factor, say, 19.0001,

and scale g of N with that to get an upper bound. So now we can use g of N to express the complexity in Big Theta notation.

In other words, if is Big Theta of 1. This will actually be the case no matter what constant value that f would have.

So in order to describe that something is constant, we can say that it is Big Theta of 1.

I've just spent the last couple of minutes to convince you that looking at the nature of the curve would

give you the true picture of the performance. In general that is also true, but you should be aware of the caveats.

Assume that some program has the performance characteristics of Big Theta of N.

This is a straight line, and generally this means that it scales well and the execution time does not explode

for last values of N. Compare that to performance characteristics of big theta of N squared.

This is a curve that grows quickly, and generally this is a bad sign.

However, assume that the constant factors that we need to bound the re-performance as is written on the

screen here, very large numbers for the linear function, and very small numbers for the quadratic function.

This means that the program with the linear performance still uses a very high number of instructions

compared to the program with the quadratic characteristics. In fact, if these are the constants needed to

bound the actual performance of the two programs, the quadratic performing program will win until N is larger than 900.

It will, however, grow at an increasing rate and it will catch up on the linear function, that is,

the Big Theta concept is true for larger values for N, but for N smaller than 900 in this example,

the linearly performing program will be slower for this specific example, and maybe that's good enough if we

only need to run our program for such small inputs.