Coding

# Simple explanation of Asymptotic Notation!

• 00:00:00 hi guys this is Keith galley and in this
• 00:00:03 video I'll be giving a brief explanation
• 00:00:05 on asymptotic notation and its role in
• 00:00:08 computer science and more specifically
• 00:00:10 algorithms so what is asymptotic
• 00:00:13 notation well in computer science we
• 00:00:16 often want to know how fast a program
• 00:00:19 process or algorithm runs however this
• 00:00:23 isn't always easy because each one of
• 00:00:25 our computers has different hardware
• 00:00:27 capabilities as a result asymptotic
• 00:00:31 notation was developed to provide a
• 00:00:33 universal way to measure the speed and
• 00:00:39 efficiency of an algorithm the second
• 00:00:46 part I think that is really important to
• 00:00:48 remember about asymptotic notation is
• 00:00:51 that it refers to large inputs so what I
• 00:00:58 mean by this is that imagine you are
• 00:01:00 sorting 10 numbers maybe one algorithm
• 00:01:03 works really well in these 10 numbers
• 00:01:06 but if you increase the size of the list
• 00:01:09 of numbers that you tried to sort to a
• 00:01:11 hundred thousand maybe a second
• 00:01:14 algorithm works a lot better in
• 00:01:16 asymptotic notation we care about the
• 00:01:18 behavior of an algorithm as the input
• 00:01:21 size approaches infinity so we care
• 00:01:23 about these large inputs let's quickly
• 00:01:28 go over the three most important
• 00:01:30 notations that you will have to know
• 00:01:31 when taking any sort of algorithms class
• 00:01:34 the first is o of n also known as Big Al
• 00:01:39 what oh of n represents is an upper
• 00:01:43 bound so if we have the function n we
• 00:01:51 could say that it is o of N squared
• 00:01:55 because when we have a big input any
• 00:01:58 value evaluated at n would be less than
• 00:02:03 that same value a lot evaluated at n
• 00:02:07 squared so 10,000 for example is always
• 00:02:12 less
• 00:02:13 and upper bounded than 10,000 squared
• 00:02:15 etc next we have theta of n theta of n
• 00:02:22 represents a tight bound so what this
• 00:02:27 means is that you know in algorithms we
• 00:02:31 don't care about constants we really
• 00:02:32 just care about that asymptotic behavior
• 00:02:34 and when you have a really big input you
• 00:02:38 know the constants don't really matter
• 00:02:41 so let's say we have the functions and
• 00:02:43 3n in 5n well 3 n is less than it's all
• 00:02:51 going to be less than 5 n and n is
• 00:02:54 always going to be less than 3n so you
• 00:02:57 can say this function 3 n right here is
• 00:02:59 tightly bounded by n we could say that
• 00:03:02 it is theta of n so if we ignore these
• 00:03:07 constants it is lower bounded by a
• 00:03:09 function of N and it's upper valued
• 00:03:13 upper bounded by a function of n so
• 00:03:15 because it has this tight bound on n we
• 00:03:18 say it's theta of n finally we'll look
• 00:03:21 at Omega of N and as you might have
• 00:03:24 guessed this represents a lower bound
• 00:03:28 for an example let's imagine that we had
• 00:03:31 the functions and cubed and log of n
• 00:03:41 whenever we plug in a value to n cubed
• 00:03:44 it is always going to be higher than
• 00:03:47 that same value plugged it plugged in to
• 00:03:49 log n for big inputs so we can say that
• 00:03:53 n cubed is Omega of log n I apologize if
• 00:03:59 this is a little bit messy but so recap
• 00:04:02 of n is an upper bound theta of n is a
• 00:04:05 tight bound and Omega of n is a lower
• 00:04:09 bound remember these three things
• 00:04:11 because you're going to use them a ton
• 00:04:13 throughout any algorithms course one
• 00:04:15 thing that I think is important to note
• 00:04:16 about asymptotic notation is that it the
• 00:04:19 convention is that you only care about
• 00:04:22 the value in an expression that has the
• 00:04:25 highest magnitude
• 00:04:26 so in this expression that's end of the
• 00:04:28 set so when we were writing if we said
• 00:04:31 that a function was upper bounded by
• 00:04:33 this expression we would just say it is
• 00:04:35 o of n to the fifth well it wouldn't be
• 00:04:40 wrong to say that it is o of n to the
• 00:04:43 fifth plus four n to the cube plus two n
• 00:04:45 plus five that's just not how computer
• 00:04:48 scientists write this notation because n
• 00:04:50 to the fifth is the term that really
• 00:04:53 dominates and controls this expression
• 00:04:56 when you have a very large input as a
• 00:04:58 simple example on asymptotic notation
• 00:05:02 let's imagine that we have two grocery
• 00:05:04 lists the grocery lists on the left it
• 00:05:07 is sorted alphabetically so so you have
• 00:05:16 on the bottom the list on the right it
• 00:05:18 is sorted completely randomly we don't
• 00:05:22 know where any item will fall on that
• 00:05:23 list and let's say we have a total of n
• 00:05:27 items all right now we wanted to figure
• 00:05:33 out which of these lists is a better way
• 00:05:35 to you know make a grocery list is it
• 00:05:38 more quickly quick to make it
• 00:05:40 alphabetical or is it more quick to make
• 00:05:42 it random so let's say we are looking
• 00:05:45 for a specific item such as cucumbers in
• 00:05:48 the list on the left we can quickly find
• 00:05:51 cucumbers by going to seas and seeing
• 00:05:53 that cucumbers is right there so we can
• 00:05:56 say that it is lower bounded by a
• 00:05:59 constant number of operations and so as
• 00:06:05 I mentioned in the previous slide lower
• 00:06:08 bound is represented by Omega so we
• 00:06:10 could say that this is omega of 1 1
• 00:06:12 represents a constant number of
• 00:06:14 operations however we might not always
• 00:06:17 get so lucky to have cucumbers be
• 00:06:19 sitting right there as the only item
• 00:06:22 that begins with a C let's imagine that
• 00:06:25 we had hundreds of thousands of items
• 00:06:28 that began with a C on our grocery list
• 00:06:30 let's say they like oh no I was shopping
• 00:06:33 for a lot of people so we had hundreds
• 00:06:35 of thousands of C
• 00:06:36 if this is the case then simply going
• 00:06:40 down to the sea part of our grocery list
• 00:06:43 wouldn't be enough to you know find
• 00:06:45 cucumbers we would have to go further
• 00:06:47 and break our list down even further to
• 00:06:49 find cucumbers so we would maybe have to
• 00:06:52 look at CEO and try to figure out you
• 00:06:56 know what items begin with CEO to find
• 00:06:58 cucumbers and then if we still had a lot
• 00:07:00 of items that begin with Cu
• 00:07:03 we'd have to continue this process and
• 00:07:05 break the list down even further into
• 00:07:08 items that begin with C you see the
• 00:07:12 process of breaking down a list into
• 00:07:14 smaller and smaller lists sort through
• 00:07:16 can be called acid or logarithmic time
• 00:07:21 in computer science so we can say that
• 00:07:24 this is upper bounded and the upper
• 00:07:27 bound is is on the worst-case scenario
• 00:07:31 so the worst case scenario we had a
• 00:07:32 bunch of items that begin with C and
• 00:07:34 maybe a bunch of them started with C or
• 00:07:36 C 1 I mean how to continue this process
• 00:07:39 for a while so the upper bound of this
• 00:07:41 is log of n as I mentioned in the
• 00:07:44 previous slide log of n can be noted Oh
• 00:07:47 noted the upper bound can be donated
• 00:07:50 with Big O this is Big O and we can say
• 00:07:53 this is Big O of log n so this Big O
• 00:07:57 means upper bound and log N is because
• 00:08:01 there's n total items in each time we
• 00:08:03 make a step further and trying to find
• 00:08:05 cucumbers we break the list down into
• 00:08:07 smaller and smaller lists on the other
• 00:08:10 hand let's imagine that we wanted to try
• 00:08:12 to find the same word the same item
• 00:08:14 cucumbers in this randomly sorted list
• 00:08:17 to do this wouldn't be as easy as the
• 00:08:21 list on the Left we would have to go
• 00:08:24 through zucchini apples soup and just
• 00:08:27 keep going down this list until we
• 00:08:29 eventually found cucumbers somewhere
• 00:08:32 down here or maybe it was up here you
• 00:08:34 know we don't know but in the worst case
• 00:08:36 we'd have to go through this whole
• 00:08:37 entire list because we don't know where
• 00:08:39 cucumbers would fall because there's no
• 00:08:41 order to how this list is sorted so in
• 00:08:44 this case we could say it is upper
• 00:08:46 bounded
• 00:08:49 by n so it is Oh again is upper bounded
• 00:08:55 and n is because we have to look through
• 00:08:58 all n items in the worst case to find
• 00:09:01 cucumbers so the right list has a upper
• 00:09:05 bound of oh of n now we know to upper
• 00:09:10 bounds we know that the list on the left
• 00:09:14 has an upper bound of oh of log n then
• 00:09:21 the list on the right so this is the
• 00:09:24 left list on the right has an upper
• 00:09:26 bound of o of n so as a result of that
• 00:09:32 we could say that alphabetical grocery
• 00:09:36 list is asymptotically faster than the
• 00:09:43 randomly sorted list