Hey guys, in this video I'm going to go over an average case analysis example.
This one is for inserting into the sorted array where, when you insert to the array,
the highest priority element is inserted at the end.
We are given that all the positions for the new element are equally likely, so the probability
will be the same for any index, and we are assuming that we don't have to worry about
resizing.
You can compare this problem to the previous video I just did on doing an amortized cost
analysis in that it's a little bit similar.
We're going to do a table and then figure out a formula and basically what we want as
the final answer is something in big O notation.
For average case analysis, the formula you use is basically you do a big sigma notation
for summing over all the elements of i where you have the probability of i times the cost
of i.
So let's go ahead and do this problem.
We're going to have values of i, we're going to have the probability of i, and the cost
of i.
For i, you can start at 1 or 0.
I guess since it's an array, I'll start at 0.
So 0, 1, 2, 3...and it'll go up to n.
For the probability of i, we're given that all the new positions would be equally, so
if we have an array of n elements, and then we're adding to that array--if you had an
array of n elements and they're all equally likely, the probability would be 1/n--and
since we're adding an element every time we add to the array, the probability is going
to be 1/(n+1).
And so this will be true for every value at any position.
So the probabilities will always be 1/(n+1).
The cost in contrast will depend on the position.
If you're adding to a sorted array, if you're adding in the middle for example, you have
to shift all the values that are under it to the right.
So the farther to the right you're adding to the array, the less of the cost it will
be.
So hopefully that makes sense.
If you're adding to the very end of the array, the cost is just going to be 1, which
is the smallest cost that you can have.
In contrast, if you're adding to the array a new first element, then you have to add
that element and shift the other n elements that we're already in the array.
That would mean that the cost would be n+1 and likewise, if you're adding to the first
index, then that's going to be just n because you're not shifting the zero index.
So it would be 1 less than (n+1) and this basically decreases until you get 2 and then
1 for adding to the end of the array.
And so that's kind of the pattern of what the cost would be to adding to a sorted array
when the order is ascending.
So we have a little table and from there, we can fill out or we can do the average case
analysis of it.
So our array starting from 0 to n, and we have the probability of i and we need to figure
out a formula for the cost of i.
So that's going to be from 0 to n.
The probability, we just said was 1/(n+1) and that's basically constant for any value.
Now we have to figure out basically how you would write this as a formula.
Hopefully, it makes sense that when i=0 we have n+1 and when it's n, we just have 1.
So you can write it as n+1-i because when i is n, you do n+1-n, so that's 1, and when
i is 0 we have n+1.
So we can use that as the formula for the cost of adding to the i index.
So it's going to be 1/(n+1) times (n+1-i) and it depends on--the formula always changes
depending on what the problem is asking you--so it's just kind of you have to look at it
and figure it out.
Again, the end result we want to have big O notation.
So our variable that we want to consider is n, even though here it's a constant.
Basically, what I'm getting at is you want to rewrite this and not all these problems
involve that much math but this one involves a little bit of math in that you want to get
rid of the i so that you have it in just n's and that way you can take the--or basically
find the big O notation of the n's, if that makes sense.
So with big sigma notation, any time you have a constant you can pull it out of the formula
or put it in front of the sigma basically.
So we can take out the 1/(n+1) because in this case what's changing and what's variable
is the i.
So we can pull that out as a constant and then we have 1/(n+1) from 0 to n times (n+1-i).
And from there we still have to get rid of the i.
So if we look at this, this is basically say that we have 1/(n+1) and then we have n+1
plus just the same as above, so (n+1)+n+n-1...+2+1.
So if we want to rewrite this, another way of thinking about this would be that this
is i when i is from 1 to n+1.
So i goes up 1, 2, 3... to n to n+1 and this is all summation, so it doesn't matter that
the order is switched.
A reason you would do that would be because and this is true because--you can just know
this from the principle of mathematical induction--there's a formula that says when you have
i from 1 to n, that this is equal to n times (n+1) over 2.
So basically when you take the series 1+2+...+n = this.
That's kind of a well known formula.
So this as you can see, removes the i and you have--and it removes the summation as well.
So you would be able to write this formula now in just terms of n's.
So we have 1/(n+1) and then we have--so this one's a little bit different, we have (n+1)
instead of just n--so this would be times (n+1) times (n+1)+1 over 2.
Sorry if that's a little sloppy.
So basically that would be 1/(n+1) times (n+1) times (n+2) over 2.
With this, the numerator and the denominator cancel out, so you get (n+2)/2 and obviously
in that case you know that the big O notation is going to just be O(n) and that would be
your final answer.
So we're done with this problem.
*chiptune music*