[MUSIC]

We have a vague understanding that Britney's approach is better in most cases

but just like with linear search, it helps to visualize this.

Much like we did with linear search when determining the efficiency of

an algorithm, and

remember we're still only looking at efficiency in terms of time.

Time complexity as it's called.

We always want to evaluate how the algorithm performs in the worse case

scenario.

Now you might be thinking that of that doesn't seem fair because given a series

of data, if the target value we're searching for

is somewhere near the front of the list then linear

search may perform just as well if not slightly better than binary search.

And that is totally true.

Remember a crucial part of learning algorithms is understanding what works

better in a given context.

When measuring efficiency though, we always use the worse case scenarios as

a benchmark, because remember, it can never perform worse than the worse case.

Let's plot these values on the graph we started earlier, with the number of tries

or the runtime of the algorithm on the y-axis, and the maximum number of values

in the series, or n on the horizontal axis to represent the worst case scenario.

We have two data points.

When n equals 10, Britney took four tries using binary search.

And when n equals 100, it took seven tries, but

even side by side, these data points are sort of meaningless.

Remember that,

while there's quite a difference between the runtime of linear search and

binary search at an n value of 100, for a computer, that shouldn't matter.

What we should check out is how the algorithm performs at levels of n that

might actually slow a computer down.

As n grows larger and larger, how do these algorithms compare to one another?

Let's add that to the graph.

[SOUND] Okay, now a picture starts to emerge.

As n gets really large,

the performance of these two algorithms differs significantly.

The difference is kind of staggering, actually.

Even with the simple gain, we saw that binary search was better, but now,

we have a much more complete idea of how much better.

For example, when n is 1,000, the runtime of linear search measured

by the number of operations or turns is also 1,000.

For binary search, it takes just 10 operations.

Now let's look at what happens when we increase n by factor of 10.

At 10,000,

linear search takes 10,000 operations while binary search takes 14 operations.

An increase by a factor of 10 in binary search only needs four more

operations to find the value.

If we increase it again by a factor of ten once more,

to an n value of 100,000, binary search takes only 17 operations.

It is blazing fast.

What we've done here is plotted on a graph how the algorithm performs

as the input set it is working on increases.

In other words, we've plotted the growth rate

of the algorithm also known as the order of growth.

Different algorithms grow at different rates, and by evaluating their growth

rates, we're getting much better picture of their performance.

Because we know how the algorithm will hold up as n grows larger.

This is so important.

In fact, it is the standard way of evaluating an algorithm, and

brings us to a concept called big O.

You might have heard this word thrown about.

And if you found it confusing, don't worry.

We've already built a definition in the past few videos.

We just need to bring it all together.

Let's start with a common statement you'll see in studies on algorithms.

Big O is a theoretical definition of the complexity of an algorithm

as a function of the size.

Wow, what a mouthful.

This sounds really intimidating but it's really not.

Let's break it down.

Big O is a notation used to describe complexity.

And what I mean by notation is that it simplifies everything we've

talked about down into a single variable.

An example of complexity written in terms of big O looks like this.

As you can see, it starts with an upper case letter O,

that's why we call it big O.

It's literally a big O.

The O comes from order of magnitude of complexity.

So that where we get the big O from.

My complexity here refers to the exercise we have been carrying out in measuring

efficiency.

If takes Britney 4 tries when n is 10,

how long does the algorithm take when n is 10 million?

When we use big O for this, the variable used which we'll get to,

distills that information down so that by reading the variable, you get a big

picture view without having to run through data points and grasps just like we did.

It's important to remember that complexity is relative.

When we evaluate the complexity of the binary search algorithm,

we're doing it relative to other search algorithms, not all algorithms.

Big O is a useful notation for understanding both time and

space complexity.

But only when comparing amongst algorithms that solve the same problem.

The last bit in the definition of big O is a function of the size, and

all this means is that big O measures complexity as the input size grows.

Because it's not important to understand how an algorithm performs in

a single data set.

But in all possible data sets.

[SOUND] You will also see big O referred to as the upper bound of the algorithm.

And what that means is that big O measures how the algorithm performs in

the worst case scenario.

So that's all they go is, nothing special.

Is just a notation that condenses the data points and graphs.

So we've built up down to one variable.

Okay, so what do these variables look like?

For John's strategy, linear search, we say that it has a time complexity of big O and

then n, so that's again big O with an n inside parentheses.

For Britney's strategy, binary search, we say that it has a time complexity of big

O of log n, that's big O with something called a log and an n inside parentheses.

Now don't worry if you don't understand that.

We'll go into that in more detail later on in the course.

Each of these has a special meaning but

it helps to work through all of them to get a big picture view, so

over the next few videos, let's examine what are called common complexities or

common values of big O that you will run into and should internalize.