where we're looking for the runtime of more complicated code.
is how to calculate the big-O class of code that has nested for loops.
So not consecutive for loops, but one loop inside another.
So let's do an example and this example is called maxDifference.
It's a method that takes in as its argument an array of integers.
level functionality of pieces of code, so let's start with that.
don't interact too much with one another, especially when it comes to run time.
then we have the return statement at the end.
Okay, so, easy stuff first.
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.
then work our way out.
we've worked with those before.
in constant time, we're comparing the values of two entries in the array.
may not do a single operation.
two depending on the result of the test.
But one, two, those are both constant numbers.
that entire if branch is just big O of one.
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.
so, accumulate together how much time we need overall.
all the way to the end of the array.
we're doing that constant amount of work.
a constant amount of work and many times where n is the size of the array.
we drop constants, so that's big O(n) amount of work.
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.
we have to do that inner piece of work, that big O(n) amount of work.
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.
that's n squared amount of work overall.
loop by the run time of that inner for loop.
loop is repeated every single time we step through that outer for loop.
the runtime of each of the three chunks of the algorithm.
where we have consecutive pieces of code.
the total run time is just the dominant term from each of those three pieces.
big O(1) followed by big O(n squared) followed by big O(1).
it's definitely not as fast growing as n squared.
N squared definitely grows as our input size gets bigger.
it runs in big O (n squared) time.
So that's an example of dealing with nested for loops.