Original subtitles

We used the example code shown here, and as you can see, the program execution speed will be pretty

predictable and consistent given the input N. The execution time is consistently linear in the input N.

Here you see another example of a method, ContainsNeedle, that takes an integer, our needle, and a list of

integers, our haystack. The function compares all entries in the haystack with the needle, and in the case

of a match, it returns true. In case of no match, it returns false.

In this example, the execution time depends on where the needle is positioned in the haystack,

if it's present at all. If the needle is found at the first element, then the function returns immediately,

and have a complexity of Big Theta of 1. Otherwise, it may scan through the whole haystack, and if the

haystack has N elements, then the complexity will be Big Theta of N.

So the exact complexity depends on the actual input contents, and therefore it makes sense to talk about the

worst-case complexity of the program. And this is exactly what the Big O notation is all about.

Let's take a close look at this ContainsNeedle method. If the haystack contains N elements, then for each

loop will iterate through at most N elements. In each iteration it performs exactly one comparison.

And whenever it returns, we can say that it uses one instruction.

In total, we get N times 1, + 1 instructions, or just N + 1.

Let's denote that f of N. If we draw it on a graph, it looks like this.

And just like with the Big Theta notation, I now introduce another function g of N, which I set to the

most significant component in f, namely N. Now I use the constant factor, 1.5, to create an upper bound for

f, namely 1.5 g of N. As you can see, f stays under 1.5 g of N, but only when N is at least 2.

This is exactly what is needed for being Big O of g of N, that is, for f being Big O of N.

Let's formalize this a bit.

You may recognize large parts of this from the previous slide. So consider the actual complexity for our

program and denote that with f of N. Again, we need three things to exist.

The function that we will use as bound, let's denote it g of N, we need a single constant, say c.

Notice that in Big Theta we needed two constants for an upper and lower bound respectively, but now we only need one.

And last, we need the same kind of constant factor as in Big Theta, namely small n.

If we can bound f below c times g of N, whenever the input size is larger than small n, then f is set to be

Big O of g of N, and again, we normally just write whatever go of N actually is instead of writing g of N explicitly.

Recall the ContainsNeedle function, and assume that this is a representation of our haystack.

Also assume that the needle to find is 26. The ContainsNeedle method, as we saw, iterates through all

elements in the haystack to find the needle. If the haystack contains 10 elements, this requires 10

comparisons worst case, and if the haystack contains 1 million elements, it requires 1 million comparisons worst case.

If there is N elements in the haystack, then the worst-case complexity was O of N as you might remember.

There is a smarter way of performing the search, however. If we know in advance that the haystack is ordered

with the smallest element in the beginning and the largest element at the end.

We can do this ordering fast, by the way, and we'll get to that in the module about algorithms, but for now,

just assume that the haystack is ordered perhaps by magic. First, consider the middle element in the haystack.

In this case, this has the value 20. The needle is larger than 20, so we can from now on safely ignore all

elements to the left, because we know that the haystack is ordered.

In the remaining part, we find the middle element again. This has the value 30; 26 is smaller than 30,

so we can from now on safely ignore all elements to the right. We are quickly eating up the list, as you can see.

In the remaining list we find the middle element again, and this has the value of 25, which is smaller than

26, and therefore we ignore all the elements to the left. In the remaining list, which is now only one

single element wide, we find the middle element, which is trivial, and we find our needle.

So, how many comparisons is needed worst case to find the needle using this strategy?

That is the number of times we can cut the haystack in half until we reach a size of one.

But how many times is that? Let's spend a moment talking about

logarithms and return to our binary search in a short while. So, consider the product 2 times 2 times 2 and

so on 7 times. Another way to write this is 2 to the power of 7. This is 128, by the way.

If we multiply with 2 one more time, we get 2 to the power of 8, which is 256.

And one more 2 gives 2 to the power of 9, which in turn is 512. In general, if we have 2 times 2 times 2 and

so on, N times, we write it 2 to the power of N, and call it an exponential function.

It looks like this. And if you take a look at the values of the axes, you can see that it grows extremely fast.

Now we could ask what should N be in order for 2 to the power of N to give, for example, 4096?

There is a mathematical function that gives the answer to this question, and that is called the logarithm.

It is written like this. The subscript 2 is called the logarithm base and refers to the 2 from the exponential function.

Another kind of logarithm, say with base 10, refers to the exponential function 10 to the power of N and

answers what N should be in order for 10 to the power of N to be something.

But when talking algorithms and data structures, we typically use logarithms with base 2.

To answer the questions, the logarithm of 4096 is 12, because 2 to the power of 12 is 4096.

Here's a graph showing the logarithm of N, or sometimes just referred to as log N.

If you consider the values of the axes, you can see that the function grows very slowly.

In fact, it grows slower and slower for higher values of N.

Consider this tree displaying a series of doublings starting from 1 and ending at 16 after 4 doublings.

If we go upwards instead and look at the number of halvings of 16 before we get to 1, that number is the

logarithm of 16, which in turn gives 4. Let's head back to our binary search.

We left where we needed the number of halvings of N, and now we have the answer.

This is exactly the logarithm of N. So the total complexity of our binary search is something with logarithm

of N, because this was a number of comparisons, and for each comparison, we need to perform something,

which takes a number of instructions. The thing is that the exact number of instructions is actually not

that important, as long as we know that it is the same number of instructions each time.

In other words, that it is constant. I therefore just write c as a representation of any constant number,

so now that I have written c times log N as a total worst-case complexity, I can easily create an upper

bound for that expression, namely by using any larger constant, for example, c + 1.

Since this log N must multiplied with a larger constant is an upper bound, I can now write that our

complexity is Big O of log N. And this is a great worst-case guarantee.

For instance, it only takes 14 comparisons to find a needle among 10,000 entries, and only 6 comparisons more

to find a needle among 1,000,000 entries.

So, a few points about the Big O notation. One could argue that finding an upper bound is easy, it is just

to use some extremely fast-growing function, for example, 999 to the power of N, which grows faster than

almost all of our functions. But the worst-case guarantee should be relevant.

Consider this graph over some data. It could be the stock market the last hour.

Then it's certainly true that the green line is an upper bound to the graph, but just as you do not get much

information if I tell you that my car drives at most 10 billion km per hour, that green line does not provide

much information as well. The upper bound is most useful if it is related to the actual worst case scenario.

In general, we should try to find the lowest possible worst-case.

As an example, it is true that N squared + N is Big O of N to the power of 3, but Big O of N squared is more interesting.

And in general, we searched for a so-called tight bound.