Next up,

let's look at the situation we encountered with the linear search algorithm.

We saw that in the worst case scenario, whatever the value of n,

John took exactly that many tries to find the answer.

As in linear search, when the number of operations to

determine the result in the worst case scenario is at most the same as n,

we say that the algorithm runs in linear time.

We represent this as O(n).

Now, you can read that as big O of n, like I just said, or you can say linear time,

which is more common.

When we put that up on a graph against constant time and logarithmic time,

we get a line that looks like this.

Any algorithm that sequentially reads the input will have linear time.

So remember any time you know a problem involves reading every item in a list,

that means a linear runtime.

As you saw from the game we played, Britney's strategy using binary search was

clearly better, and we can see that on the graph.

So if we had the option, why would we use linear search, which runs in linear time?

Remember, that binary search had a precondition,

the inputs that had to be sorted.

While we won't be looking at sorting algorithms in this course,

as you learn more about algorithms, you'll find that sorting algorithms have varying

complexities themselves, just like search does.

So we have to do additional work prior to using binary search.

For this reason in practice linear search ends on being more peformant on

the certain value on n, Because the combination of sorting first and

then searching using binary search adds up.

The next common complexity you will hear about is when an algorithm runs in

Quadratic Time.

And the word Quadratic sounds familiar to you,

it's because you might have heard about in Math class.

Quadratic is a word that means an operation raised to the second power or

when something is squared.

Let's say you and your friends are playing a tower defense game and

to start it off you're going to draw a map of the terrain.

This map is going to be a grid and

you pick a random number to to determine how long this grid is.

Let's set n the size of the grid to 4.

[SOUND] Next, you need to come up with a list of coordinates, so

you can place towers and enemies and stuff on this map.

So, how do we do this?

If we start out horizontally, we'd have coordinate points that go (1,1),

(1,2), (1,3) and (1,4).

Then you go up one level, vertically, and we have points (2,1), (2,2),

(2,3) and (2,4).

Go up one more and you have the points (3,1), (3,2), (3,3) and (3,4).

And on that last row, you have the points (4,1), (4,2), (4,3) and (4,4).

Notice that we have a pattern here.

For each row, [SOUND] we take the value and

then create a point by adding to that every column value.

The range of values go from 1 to the value of n.

So we can generally think of it this way.

For the range of values from 1 to n, for each value in that range, we create

a point by combining that value with the range of values from 1 to n again.

Doing it this way for

each value in the range of 1 to n recreate an n number of values,

and we end up with 16 points, which is also n times n, or n squared.

This is an algorithm with a quadratic run time, because for

any given value of n, we carry out n squared number of operations.

Now, I picked a relatively easy, so to speak, example, here,

because in English, at least, we often denote map sizes by height times width.

So we would call this a four by four grid, which is just another way of saying,

four squared or n squared.

In O notation, we would write this as big O(n2), or

say that this is an algorithm with a quadratic runtime.

Many search algorithms have a worst case quadratic runtime,

which you'll learn about soon.

Now, in addition to quadratic runtimes,

you may also run into Cubic Runtimes as you encounter different algorithms.

In such an algorithm, for given value of n,

the algorithm executes n^3 number of operations.

These are as common as quadratic algorithms though, so

you won't look at any examples, but I think it's worth mentioning.

Thrown up on our graph [SOUND] quadratic in cubic run times look like this.

So this is starting to look pretty expensive computationally as they say.

We can see here that for small changes in n is a pretty significant change in

a number of operations that we need to carry out.