For each neighbor h of j do, how many neighbors can, can j have okay?

In the worst case for

some, for some nodes we might have n minus one, at most n minus one.

Of course, we have, when we are talking about an adjacency list.

There is a given number of neighbors for every node.

But again, as we said, we are not trying to get at the exact number of steps here.

We are going to get an approximation.

So I can approximate things and say this loop, this this line here, for

a node j, I can have, at most, in minus one neighbors.

Okay?

In a graph that has n nodes, every node has, at most.

N minus one neighbors.

so this one here I can say it's all of N, okay?

Because N minus one is all of N.

This statement here, the if statement is, is a simple, condition to test.

It's just a fixed amount of time.

This is simple assignment here is, fixed amount of time,

that adding something to the Q is also fixed amount of time.

The return is o of 1, okay?

So now that we have these numbers for

every line, how long does this algorithm take, okay?

So we have o of 1 here.

[NOISE] Then we have this loop here is going to take.

O(n).

This one, this line here is going to take O(1).

These two, combined, they are going to take O(1), okay?

Now, we have this big one here, okay?

How long is going to take?

This is going to iterate n times, n times, and in each iteration,

we are going to be doing also n times plus sum constant.

So, we know now that this is going to be on the order of n squared.

Okay? So these constants can go away,

this constant, these constants and so on.

So it's order of n times order of n is going to give me order of n squared.

And this line here, is just 0(1).

So now I can just sum these numbers,

I say its 0(1) plus 0(n) plus 0(1) plus 0(n) squared plus 0(n), 0(1).

This is going to give me that the algorithm takes.

[SOUND] Again it's O of n plus O plus n squared but,

we focus on the dominating terms.

n squared is a dominating one here.

So, [COUGH] by using this analysis we get that algorithm, is O of n squared.

So this is our first attempt at analyzing the efficiency of this algorithm, and

as you can see this is a very efficient algorithm.

It takes quadratic amount of time in the, in the number of notes in the graph.

So like before when we focused on when we looked at Brute force algorithm.

For computing distances, remember that even for, for 250 naughts or

something like that the algorithm would have taken ten to the 59 years.

If you have 250 naughts and it's going to perform in the order of

250 squared this is going to be done in fractions of a second.

In, in, in today's computers okay.

So this is a very efficient algorithm.

And this is using our first attempt at analyzing running

time that we get an O events squared time, so

we can say that bvs takes a quadratic time in the number of nodes