Hi everybody and welcome back to our data structures and algorithms video series. In our
last video we learned about complexity analysis and in this video we're going to learn how to
determine the best average and worst case for our algorithms. If we truly want to get a handle
on complexity for our more complicated algorithms we need to distinguish between these three cases.
So, the three cases are best average and worst cases best case would be when the algorithm takes
the fewest number of steps possible worst case would be when the algorithm takes the
maximum number of steps possible an average is a performance that falls between those two extremes
average performance and worst case performance are the most used algorithm analysis
but don't discount best case best case performance does have its uses
when basically when the best case of an individual task is
known it can be impr it can be used to improve the accuracy of an overall worst case analysis
In order to determine the average case we need to weigh the number of steps that occur for
any given input by the probability of that input incur occurring
and then we do a sum of it over the number of inputs. This is called expected value.
This assumes the possibilities can be determined and the distribution is known
because p is the probability distribution it ends up satisfying two constraints
that the function p can never be to negative and the sum of all the probabilities should equal
one right one hundred percent let's look at an example and determine the
best average and worst case of that algorithm so in the first example we are going to determine the
worst case of the algorithm in this case our algorithm we are searching within an integer array
that is the size of n searching through this size and we're trying to find x in order to determine
the worst case we must know the case that causes the maximum number of operations to be executed
in this case let's think what would be the worst case worst case would be that x right here doesn't
exist in the array so we would just keep going through the for loop for the count of n
and return negative one so the worst case in this example is linear time which would be
away right so it's basically our big o analysis now before we jump into solving
the average case let's determine what the best case would be for this example
best case essentially is calculating the lower bound of running of the running time
for our algorithm so in this case the best case occurs when x is the first item in our array when
x is basically when the array is zero this would be done in constant time which would be a one
so now it's time to find the average case in order to find the average case we need to assume that
all the cases just finding any version of x is uniformly distributed all possible cases would be
n right so if we're looking for an item we can go to it potentially here
n times because x could be the last element in n n could also not exist and this is a constant time
which is plus one so the entire search is n plus 1. when we're saying something is going to be
uniformly distributed we're saying that when we are looking for the element x
it's going to be universal uniformly distributed amongst n plus 1. so
the requirement would need to be in the position or doesn't exist which means it would
be between one and n plus one being uniformly distributed we're saying that we're finding
e of x where we're looking for one
and one could be within the probability of one over n plus one plus two over one n plus one plus
three one over n plus one so on and so forth all the way to n plus one which is one and times one
over n plus one this is our probability this is the input that we are looking for this
using some fun math that would be required if you uh do some calculus this is our summation so
when we are going through this we are summing up all the way to n
n plus one this can be translated as n plus one times n plus 2 all over 2 n plus 1.
so we look at this here we could cancel out our n plus 1 it's n plus one
it's n plus two over two which translates to an average case of being linear time
this is our average case so in this example our average case and our worst case are actually the
same now let's talk about another complexity and that's amortized complexity amortized analysis is
used for algorithms where an occasional operation is very slow but for most of the other operations
it's faster so in this case we analyze a sequence of operations and we need to
guarantee a worst case average time which is lower than the worst case time of a expensive operation
the idea here is that while some operations may be costly they do not occur frequently enough
to bias the entire program and this is because less costly operations will end up outnumbering
the costly ones in the long run basically paying back the program over
a certain number of iterations so let's think about this in less abstract of an example
you make a certain amount a year and your monthly expenses need to be less than
that amount that you make in a year divided by 12. so you can only spend a certain amount of money
in a particular month but if you need to buy a car and that's more expensive then you actually end up
offsetting that because you spend a big amount of money in one month but in the other months
you're going to be saving money for that expensive month that's what we're doing here we're saving
time with our less costly operations so that we can prepare for a costly operation operation in
the long run so let's think about something in the terms of a table we want to determine the size of
the table in this example we're going to do a hash table there's trade-offs between space and time
if we make a hash table really big the search time becomes fast but the space required for it is very
high so how do we determine then the best size for our table the solution is to do a dynamic ray
application which means that we double the size of the ray each time it fills up so what does
this mean let's draw it out so initially our table is empty which means it has a size of zero
then we want to insert an item in this case it's gonna be an overflow because our size is zero
so we start off and make our array have one item we're going to insert one
then we want to insert two this is going to cause an overflow again so we double
our array so our array is the size of one so we double it it now has
two so we have one and two now we want to insert three so we do insert for three well there's an
overflow we're going to double the size so in this case we have one two three and then a free space
so when we insert four we will not overflow so we insert in four
we're going to have space to put four in one two 3 4. when we want to add 5 though
again we get an overflow so we double the size of our array in this case now becomes 8
two three four five so we can insert in six and then seven the eight our next overflow
would end up when we want to insert in 9 and then we would double the array
to the 16. so what are the steps that are occurring here we're allocating memory for
a larger table um and this is in the case that the size is going to become twice that of the old
table we copy the contents of the old table to the new table and then we free up the old table space
worst case where all an insertion could cost o n it could be linear because we have to copy
everything over to the next table but when we want to insert a new value like when we inserted in 4
here or we insert 6 7 and 8 that can be done in constant time so in this example the worst case
is o n
but all the remaining insertions done afterwards can be done in constant time which is one which is
our best as the remaining insertions can be done in this constant time a sequence of n insertions
can always be done in o n time so therefore n insertions can be completed in o and time because
worst case our first one goes o n all the remaining insertions are going to be one
o n plus a bunch of o once is still o n the amortized time is properly operation correct
amortize time per operation we're looking at then o n over n which means overall this
is o one time so now you've seen a working example showing how amortized complexity works
this is using what we've already learned within our first video about complexity analysis and
then adding on best worst and average cases in our next video we are going to learn about
p and np if you like what you saw please make sure you subscribe to my channel
so that you can get notified when i upload another video for this data structures and algorithms
series or anything else that you find interesting on my channel happy learning