So now that you've looked at what max difference does as a method,

let's analyze its performance.

And as we did before, it's useful to chunk up the method into the pieces that really

don't interact too much with one another, especially when it comes to run time.

And so for this context we have the initialization piece at the beginning,

then we have some nested piece of code in the middle, and

then we have the return statement at the end.

Okay, so, easy stuff first.

Let's look at the beginning at the end and

these are single instructions that get executed in constant time.

And so, each of those we don't need to worry about.

And let's focus in on really the meaty part of this method.

And we've got a for loop within a for loop.

And so, it might be a little bit daunting.

How do we analyze its run time?

And so a rule of thumb is to count from the inside out.

And so let's go as far, as deep into the nesting as we can and

then work our way out.

And so inside the inner for loop, we have an if branch and

we've worked with those before.

And so we notice that what happens here is we're doing a test that can happen

in constant time, we're comparing the values of two entries in the array.

And then, based on the result of that test, we may or

may not do a single operation.

And so, that entire conditional statement will either be one operation or

two depending on the result of the test.

But one, two, those are both constant numbers.

They don't depend on the size of the input, and so

that entire if branch is just big O of one.

And so, the advantage of working from inside out is that now we don't need to

worry about what operations we had over there, or what code we executed.

All we need to worry about Is that it was a big O of one piece of the program.

And so now, we can work our way back up to say how many

times does that big O of one piece of work have to get repeated and executed and

so, accumulate together how much time we need overall.

Okay so, in the inner for loop, what we're doing is we're going from j=0,

all the way to the end of the array.

So we're stepping through the input array, and at each point,

we're doing that constant amount of work.

And so that means that if we're focusing in on that inner for loop, we're doing

a constant amount of work and many times where n is the size of the array.

And so, overall, we're doing a constant times n amount of work, but

we drop constants, so that's big O(n) amount of work.

So that inner for

loop, every time we go through it, we're doing a big O(n) amount of work.

Now how many times do we go through that inner for loop?

Well, let's step back out one more level and we've got the outer for loop.

And so that outer for loop you can think of as going through the entire array,

from i=0 to the end of the array, and for each new value of i,

we have to do that inner piece of work, that big O(n) amount of work.

Okay, so every time we go through the outer for

loop, we're doing O(n) amount of work.

How many times do we go through the outer for loop?

Well the length of the array many times.

So that's n many times.

And so n many times do we do O(n) amount of work,

that's n squared amount of work overall.