Full transcript of “Algorithms and Data Structures Tutorial - Full Course for Beginners”. Click a timestamp to open the video at that moment. Need another video? Use the YouTube transcript generator.
0:00 this is a full-length course from treehouse we at free code camp are longtime fans of their learning platform they were kind enough to let our non-profit make this course freely available on our youtube channel if you like this course treehouse has a lot more courses like this one the link is in the description along with time codes to the different sections in this course [Music] hi my name is passan i'm an instructor here at treehouse and welcome to introduction to algorithms whether you are a high school or college student a developer in the industry or someone who is learning to code you have undoubtedly run into the term algorithm for many people this word is kind of
0:46 scary it represents this body of knowledge that seems just out of reach only people with computer science degrees know about algorithms now to others this brings up feelings of imposter syndrome you might already know how to code but you're not a real developer because you don't know anything about algorithms personally it made me frame certain jobs as above my skill level because the interview contained algorithm questions well whatever your reasons are in this course our goal is to dispel all those feelings and get you comfortable with the basics of algorithms like any other subject i like to start my courses with what the course is and is not in this course we're going to cover the very basic set of knowledge that you
1:32 need as a foundation for learning about algorithms this course is less about specific algorithms and more about the tools you will need to evaluate algorithms understand how they perform compare them to each other and make a statement about the utility of an algorithm in a given context now don't worry none of this will be theoretical and we will learn these concepts by using well-known algorithms in this course we will also be writing code so i do expect you to have some programming experience if you intend to continue with this topic you can definitely stick around even if you don't know how to code but you might want to learn the basics of programming in the meantime in this course we will be using the python programming language python reads
2:17 a lot like regular english and is the language you will most likely encounter when learning about algorithms these days if you don't know how to code or if you know how to code in a different language check out the notes section of this video for links to other content that might be useful to you as long as you understand the fundamentals of programming you should be able to follow along pretty well if you're a javascript developer or a student who's learning javascript for example chances are good that you'll still be able to understand the code we write later i'll be sure to provide links along the way if you need anything to follow up on let's start with something simple what is an algorithm an algorithm is a set of steps or instructions for completing a task
3:04 this might sound like an over simplification but really that's precisely what an algorithm is a recipe is an algorithm your morning routine when you wake up is an algorithm and the driving directions you follow to get to a destination is also an algorithm in computer science the term algorithm more specifically means the set of steps a program takes to finish a task if you've written code before any code really generally speaking you have written an algorithm given that much of the code we write can be considered an algorithm what do people mean when they say you should know about algorithms now consider this let's say i'm a teacher in a classroom and i tell everyone i have an assignment for them on their desks they have a
3:49 picture of a maze and their task is to come up with a way to find the quickest way out of the maze everyone does their thing and comes up with a solution every single one of these solutions is a viable solution and is a valid example of an algorithm the steps one needs to take to get out of the maze but from being in classrooms or any group of any sort you know that some people will have better ideas than others we all have a diverse array of skill sets over time our class picks the best of these solutions and any time we want to solve a maze we go with one of these solutions this is what the field of algorithms is about there are many problems in computer science but some of them are pretty common regardless of what project you're
4:35 working on different people have come up with different solutions to these common problems and over time the field of computer science has identified several that do the job well for a given task when we talk of algorithms we're referring to two points we're primarily saying there's an established body of knowledge on how to solve particular problems well and it's important to know what the solutions are now why is it important if you're unaware that a solution exists you might try to come up with one yourself and there's a likelihood that your solution won't be as good or efficient whatever that means compared to those that have been thoroughly reviewed but there's a second component to it as well part of understanding algorithms is not
5:22 just knowing that an algorithm exists but understanding when to apply it understanding when to apply an algorithm requires properly understanding the problem at hand and this arguably is the most important part of learning about algorithms and data structures as you progress through this content you should be able to look at a problem and break it down into distinct steps when you have a set of steps you should then be able to identify which algorithm or data structure is best for the task at hand this concept is called algorithmic thinking and it's something we're going to try and cultivate together as we work through our content lastly learning about algorithms gives you a deeper understanding about complexity and efficiency in programming
6:08 having a better sense of how your code will perform in different situations is something that you'll always want to develop in hone algorithmic thinking is why algorithms also come up in big tech interviews interviewers don't care as much that you are able to write a specific algorithm in code but more about the fact that you can break a seemingly insurmountable problem into distinct components and identify the right tools to solve each distinct component and that is what we plan on doing in this course though we're going to focus on some of the tools and concepts you'll need to be aware of before we can dive into the topic of algorithms if you're ready let's get started hey again in this video we're going to do something unusual we're going to play
6:54 a game and by we i mean me and my two friends here brittany and john this game is really simple and you may have played it before it goes something like this i'm going to think of a number between 1 and 10 and they have to guess what the number is easy right when they guess a number i'll tell them if their guess is too high or too low the winner is the one with the fewest tries all right john let's start with you i'm thinking of a number between one and ten what is it between you and me the answer is three uh quick question does the range include one and ten that is a really good question so what john did right there was to establish the bounds of our problem no solution works on every problem and an important part of algorithmic thinking is to clearly define what the problem set is and clarify what values
7:40 count as inputs yeah 1 and ten are both included is it one too low is it two too low is it three correct okay so that was an easy one it took john three tries to get the answer let's switch over to brittany and play another round using the same number as the answer okay brittany i'm thinking of a number between 1 and 10 inclusive so both 1 and 10 are in the range what number am i thinking of is it 5 too high 2 too low is it 3 correct all right so what we had there was two very different ways of playing the same game somehow with even such a simple game we saw different approaches to figuring out a solution to go back to algorithmic thinking for a second this means that with any given problem there's no one best solution
8:27 instead what we should try and figure out is what solution works better for the current problem in this first pass at the game they both took the same amount of turns to find the answer so it's not obvious who has the better approach and that's mostly because the game was easy let's try this one more time now this time the answer is 10. all right john you first is it one too low is it two still too low is it three too low is it four too low is it five still too low is it six too low is it seven too low is it eight low is it nine do low is it ten correct you got it okay so now same thing but with britney this time is it five too low eight too low is it nine still too low it's ten
9:13 all right so here we start to see a difference between their strategies when the answer was three they both took the same number of turns this is important when the number was larger but not that much larger 10 in this case we start to see that britney strategy did better she took four tries while john took 10. we've played two rounds so far and we've seen a different set of results based on the number they were looking for if you look at john's way of doing things then the answer being 10 the round we just played is his worst case scenario he will take the maximum number of turns 10 to guess it when we picked a random number like three it was hard to differentiate which strategy was better because they both performed exactly the same but in john's worst case scenario a
9:58 clear winner in terms of strategy emerges in terms of algorithmic thinking we're starting to get a sense that the specific value they're searching for may not matter as much as where that value lies in the range that they've been given identifying this helps us understand our problem better let's do this again for a range of numbers from one to one hundred we'll start by picking five as an answer to trick them okay so this time we're going to run through the exercise again this time from one to one hundred and both one and one hundred are included is it one at this point without even having to run through it we can guess how many tries john is going to take since he starts at one and keeps going he's going to take five tries as we're about to see is it five cool correct okay now for brittany's turn
10:43 is it 50 too high is it 25 still too high is it 13 too high is it seven too high is it four too low is it six too high is it five correct let's evaluate john took five tries brittany on the other hand takes seven tries so john wins this round but again in determining whose strategy is preferred there's no clear winner right now what this tells us is that it's not particularly useful to look at the easy answers where we arrive at the number fairly quickly because it's at the start of the range instead let's try one where we know john is going to do poorly let's look at his worst case scenario where the answer is 100 and see how britney performs in such a scenario
11:28 okay john let's do this one more time one through 100 again is it one we can fast forward this scene because well we know what happens john takes 100 tries hi brittany you're up is it 50 too low is it 75 too low 88 too low 94 too low is it 97 too low 99 too low 100. okay so that took brittney seven turns again and this time she is the clear winner if you compare their individual performances for the same number set you'll see that britney's approach leaves john's in the dust when the answer was five so right around the start of the range john took five turns but when the answer was 100 right at the end of the range he took 100 tries it took him 20 times the amount of
12:15 tries to get that answer compared to britney on the other hand if you compare britney's efforts when the number was 5 she took seven tries but when the number was 100 she took the same amount of tries this is pretty impressive if we pretend that the number of tries is the number of seconds it takes britney and john to run through their attempts this is a good estimate for how fast their solutions are ok we've done this a couple times and brittany and john are getting tired let's take a break in the next video we'll talk about the point of this exercise in the last video we ran through an exercise where i had some of my co-workers guess what number i was thinking so was the point of that exercise you might be thinking hey i thought i was here to learn about algorithms the exercise we just did was an example
13:01 of a real life situation you will run into when building websites apps and writing code both approaches taken by john and brittany to find the number i was thinking of are examples of searching for a value it might be weird to think that there's more than one way to search but as you saw in the game the speed at which the result was obtained differed between john and brittany think about this problem from the perspective of a company like facebook at the time of this recording facebook has 2.19 billion active users let's say you're traveling in a different country and meet someone you want to add on facebook you go into the search bar and type out this person's name if we simplify how the facebook app works it has to search across these 2.19
13:47 billion records and find the person you are looking for the speed at which you find this person really matters imagine what kind of experience it would be if when you search for a friend facebook put up a spinning activity indicator and said come back in a couple hours i don't think we'd use facebook as much if that was the case from the company's perspective working on making search as fast as possible using different strategies really matters now i said that the two strategies britney and john used were examples of search more specifically these are search algorithms the strategy john took where he started at the beginning of the range and just counted one number after the other is a type of search called linear search
14:33 it is also called sequential search which is a better description of how it works or even simple search since it really is quite simple but what makes his approach an algorithm as opposed to just looking for something remember we said that an algorithm is a set of steps or instructions to complete a task linear search is a search algorithm and we can define it like this we start at the beginning of the list or the range of values then we compare the current value to the target if the current value is the target value that we're looking for we're done if it's not we'll move on sequentially to the next value in the list and then repeat step 2. if we reach the end of the list then the target value is not in the list
15:20 this definition has nothing to do with programming and in fact you can use it in the real world for example i could tell you to walk into a bookstore and find me a particular book and one of the ways you could do it is using the linear search algorithm you could start at the front of the bookstore and read the cover or the spine of every book to check that it matches the book that you're looking for if it doesn't you go to the next book and repeat until you find it or run out of books what makes this an algorithm is the specificity of how it is defined in contrast to just jumping into a problem and solving it as we go along an algorithm follows a certain set of guidelines and we use the same steps to solve the problem each time we face it
16:05 an important first step to defining the algorithm isn't the algorithm itself but the problem we're trying to solve our first guideline is that an algorithm must have a clear problem statement it's pretty hard to define an instruction set when you don't have a clear idea of what problem you're trying to solve in defining the problem we need to specify how the input is defined and what the output looks like when the algorithm has done its job for linear search the input can be generally described as a series of values and the output is a value matching the one we're looking for right now we're trying to stay away from anything code related so this problem statement definition is pretty generic but once we get to code we can actually tighten this up once we have a problem an algorithm is a
16:51 set of steps that solves this problem given that the next guideline is that an algorithm definition must contain a specific set of instructions in a particular order we really need to be clear about the order in which these instructions are executed taking our simple definition of linear search if i switched up the order and said move sequentially to the next value before specifying that first comparison step if the first value were the target one our algorithm wouldn't find it because we moved to the second value before comparing now you might think okay that's just an avoidable mistake and kind of common sense the thing is computers don't know any of that and just do exactly as we tell them so specific order is really important
17:38 the third guideline is that each step in our algorithm definition must not be a complex one and needs to be explicitly clear what i mean by that is that you shouldn't be able to break down any of the steps into further into additional subtasks each step needs to be a distinct one we can't define linear search as search until you find this value because that can be interpreted in many ways and further broken down into many more steps it's not clear next and this one might seem obvious but algorithms should produce a result if it didn't how would we know whether the algorithm works or not to be able to verify that our algorithm works correctly we need a result now when using a search algorithm the end result can actually be nothing which
18:25 indicates that the value wasn't found but that's perfectly fine there are several ways to represent nothing in code and as long as the algorithm can produce some results we can understand its behavior the last guideline is that the algorithm should actually complete and cannot take an infinite amount of time if we let john loose in the world's largest library and asked him to find a novel we have no way of knowing whether he succeeded or not unless he came back to us with a result okay so quick recap what makes an algorithm an algorithm and not just something you do one it needs to have a clearly defined problem statement input and output when using linear search the input needs to be just a series of values but to actually use brittany's strategy there's
19:12 one additional precondition so to speak if you think about her strategy it required that the numbers be sorted in ascending order this means that where the input for john is just a series of values to solve the problem the input to brittany's algorithm needs to be a sorted series of values so clearly defined problem statement clearly defined input and clearly defined output second the steps in the algorithm need to be in a very specific order the steps also need to be distinct you should not be able to break it down into further subtasks next the algorithm should produce a result and finally the algorithm should complete in a finite amount of time these guidelines not only help us define
19:58 what an algorithm is but also helps us verify that the algorithm is correct executing the steps in an algorithm for a given input must result in the same output every time if in the game i played the answer was 50 every time then every single time john must take 50 turns to find out that the answer is 50. if somehow he takes 50 turns in one round then 30 the next and we technically don't have a correct algorithm consistent results for the same set of values is how we know that the algorithm is correct i should stress that we're not going to be designing any algorithms on our own and we'll start off and spend most of our time learning the tried and true algorithms that are known to efficiently
20:45 solve problems the reason for talking about what makes for a good algorithm though is that the same set of guidelines makes for good algorithmic thinking which is one of the most important skills we want to cultivate when we encounter a problem before rushing in and thinking about solutions what we want to do is work through the guidelines first we break down the problem into any possible number of smaller problems where each problem can be clearly defined in terms of an input and an output now that we know how to generally define an algorithm let's talk about what it means to have a good algorithm an important thing to keep in mind is that there's no one single way to measure whether an algorithm is the right solution because it is all about context
21:30 earlier we touched on two concepts correctness and efficiency let's define correctness more clearly because before we can evaluate an algorithm on efficiency we need to ensure its correctness before we define our algorithms we start by defining our problem in the definition of that problem we have a clearly defined input satisfying any preconditions and a clearly defined output an algorithm is deemed correct if on every run of the algorithm against all possible values in the input data we always get the output we expect part of correctness means that for any possible input the algorithm should always terminate or end if these two are not true then our
22:16 algorithm isn't correct if you were to pick up an algorithm's textbook and look up correctness you will run into a bunch of mathematical theory this is because traditionally algorithm correctness is proved by mathematical induction which is a form of reasoning used in mathematics to verify that a statement is correct this approach involves writing what is called a specification and a correctness proof we won't be going into that in this course proof through induction is an important part of designing algorithms but we're confident that you can understand algorithms both in terms of how and when to use them without getting into the math so if you pick up a textbook and feel daunted don't worry i do too but we can still figure things out without it
23:02 all right so once we have a correct algorithm we can start to talk about how efficient an algorithm is remember that this efficiency ultimately matters because they help us solve problems faster and deliver a better end user experience in a variety of fields for example algorithms are used in the sequencing of dna and more efficient sequencing algorithms allow us to research and understand diseases better and faster but let's not get ahead of ourselves we'll start simple by evaluating john's linear search algorithm in terms of its efficiency first what do we mean by efficiency there are two measures of efficiency when it comes to algorithms time and space sounds really cool and very sci-fi
23:48 huh efficiency measured by time something you'll hear called time complexity is a measure of how long it takes the algorithm to run time complexity can be understood generally outside the context of code and computers because how long it takes to complete a job is a universal measure of efficiency the less time you take the more efficient you are the second measure of efficiency is called space complexity and this is pretty computer specific it deals with the amount of memory taken up on the computer good algorithms need to balance between these two measures to be useful for example you can have a blazingly fast algorithm but it might not matter if the algorithm consumes more memory than you have available both of these concepts time and space
24:35 complexity are measured using the same metric but it is a very technical sounding metric so let's build up to it slowly and start simple a few videos ago i played a game with brittany and john where they tried to guess the number i was thinking of effectively they were searching for a value so how do we figure out how efficient each algorithm is and which algorithm was more suited to our purposes if we consider the number of tries they took to guess or search for the value as an indicator of the time they take to run through the exercise this is a good indicator of how long the algorithm runs for a given set of values this measurement is called the running time of an algorithm and we'll use it to define time complexity
25:21 in the game we play it four rounds let's recap those here focusing on john's performance in round one we had 10 values the target was 3 and john took 3 turns in round 2 we had 10 values the target was 10 and john took 10 turns in round 3 we had 100 values the target was john took five tries and finally in round four when the target was 100 given 100 values john took 100 tries on paper it's hard to gauge anything about this performance when it comes to anything with numbers though i like to put it up on a graph and compare visually on the vertical or y-axis let's measure the number of tries it took john to guess the answer or the running time of the algorithm on the horizontal or
26:08 x-axis what do we put for each turn we have a number of values as well as a target value we could plot the target value on the horizontal axis but that leaves some context and meaning behind it's far more impressive that john took five tries when the range went up to 100 then when he took three tries for a maximum of 10 values we could plot the maximum range of values but then we're leaving out the other half of the picture there are data points however that satisfy both requirements if we only plot the values where the target the number john was looking for was the same as the maximum range of values we have a data point that includes both the size of the data set as well as his effort
26:55 there's an additional benefit to this approach as well there are three ways we can measure how well john does or in general how well any algorithm does first we can check how well john does in the best case or good scenarios from the perspective of his strategy in the range of 100 values the answer being a low number like three at the start of the range is a good scenario he can guess it fairly quickly one is his best case scenario or we could check how well he does on average we could run this game a bunch of times and average out the running time this would give us a much better picture of john's performance over time but our estimates would be too high if the value he was searching for was at the start of the range or far too low if it was at the end of the range
27:41 let's imagine a scenario where facebook naively implements linear search when finding friends they looked at the latest u.s census saw that 50 of names start with the letters a through j which is the first 40 of the alphabet and thought okay on average linear search serves us well but what about the rest of those whose names start with the letter after j in the alphabet searching for my name would take longer than the average and much longer for someone whose name starts with the letter z so while measuring the run time of an algorithm on average might seem like a good strategy it won't necessarily provide an accurate picture by picking the maximum in the range we're measuring how our algorithm does in the worst case scenario analyzing the worst case scenario is
28:27 quite useful because it indicates that the algorithm will never perform worse than we expect there's no room for surprises back to our graph we're going to plot the number of tries a proxy for running time of the algorithm against the number of values in the range which will shorten to n n here also represents john's worst case scenario when n is 10 he takes 10 turns when n is 100 he takes 100 turns but these two values alone are insufficient to really get any sort of visual understanding moreover it's not realistic john may take a long time to work through 100 numbers but a computer can do that in no time to evaluate the performance of linear search in the context of a computer we
29:13 should probably throw some harder and larger ranges of values at it the nice thing is by evaluating a worst case scenario we don't actually have to do that work we know what the result will be for a given value of n using linear search it will take n tries to find the value in the worst case scenario so let's add a few values in here to build out this graph okay so we have a good picture of what this is starting to look like as the values get really large the running time of the algorithm gets large as well we sort of already knew that before we dig into this runtime any deeper let's switch tracks and evaluate brittany's work by having something to compare against it should become easier to build a mental model around time complexity
29:58 the algorithm john used linear search seemed familiar to us and you could understand it because it's how most of us search for things in real life anyway brittany's approach on the other hand got results quickly but it was a bit harder to understand so let's break it down just like john's approach britney started with a series of values or a list of numbers as her input where john just started at the beginning of the list and searched sequentially brittany's strategy is to always start in the middle of the range from there she asks a comparison question is the number in the middle of the range equal to the answer she's looking for and if it's not is it greater than or less than the answer if it's greater than she can eliminate all the values less than the one she's
30:43 currently evaluating if it's lesser than the answer she can eliminate all the values greater than the one she's currently evaluating with the range of values that she's left over with she repeats this process until she arrives at the answer let's visualize how she did this by looking at round three in round three the number of values in the range was 100 the answer was 5. the bar here represents the range of values one of the left 100 at the right and this pointer represents the value britney chooses to evaluate so she starts in the middle at 50. she asks is it equal to the answer i say it's too high so this tells her that the value she is evaluating is greater than our target value which means there's no point in searching any of the values to
31:30 the right of 50 that is values greater than 50 in this range so she can discard those values altogether she only has to consider values from 1 to 50 now the beauty of this strategy and the reason why britney was able to find the answer in such few turns is that with every value she evaluates she can discard half of the current range on her second turn she picks the value in the middle of the current range which is 25. she asks the same question i say that the value is too high again and this tells her that she can discard everything greater than 25 and the range of values drops from 1 to 25. again she evaluates the number in the middle roughly so that'd be 13 here i tell her this is still too high she
32:16 discards the values greater moves to value at 7 which is still too high then she moves to 4 which is now too low she can discard everything less than 4 which leaves the numbers 4 through 7. here she picked 6 which was too high which only leaves one value 5. this seems like a lot of work but being able to get rid of half the values with each turn is what makes this algorithm much more efficient now there's one subtlety to using binary search and you might have caught on to this for this search method to work as we've mentioned the values need to be sorted with linear search it doesn't matter if the values are sorted since a linear search algorithm just progresses sequentially checking every element in the list if the target value exists in
33:02 the list it will be fouled but let's say this range of values 100 was unsorted britney would start at the middle with something like 14 and ask if this value was too low or too high i say it's too high so she discards everything less than 14. now this example starts to fall apart here because well britney knows what numbers are less than 14 and greater than one she doesn't need an actual range of values to solve this a computer however does need that remember search algorithms are run against lists containing all sorts of data it's not always just a range of values containing numbers in a real use case of binary search which we're going to implement in a bit the algorithm wouldn't return the target value because we already know that it's
33:48 a search algorithm so we're providing something to search for instead what it returns is the position in the list that the target occupies without the list being sorted a binary search algorithm would discard all the values to the left of 14 which over here could include the position where our target value is eventually we'd get a result back saying the target value doesn't exist in the list which is inaccurate earlier when defining linear simple search i said that the input was a list of values and the output was the target value or more specifically the position of the target value in the list so with binary search there's also that precondition the input list must be sorted so let's formally define binary search first the input a sorted list of values
34:34 the output the position in the list of the target value we're searching for or some sort of values indicate that the target does not exist in the list remember our guidelines for defining an algorithm let me put those up again really quick the steps in the algorithm need to be in a specific order the steps also need to be very distinct the algorithms should produce a result and finally the algorithm should complete in a finite amount of time let's use those to define this algorithm step one we determine the middle position of the sorted list step two we compare the element in the middle position to the target element step three if the elements match we return the middle position and end if they don't match in step 4 we check
35:20 whether the element in the middle position is smaller than the target element if it is then we go back to step 2 with a new list that goes from the middle position of the current list to the end of the current list in step five if the element in the middle position is greater than the target element then again we go back to step two with a new list that goes from the start of the current list to the middle position of the current list we repeat this process until the target element is found or until a sub list contains only one element if that single element sublist does not match the target element then we end the algorithm indicating that the element does not exist in the list okay so that is the magic behind how britney managed to solve the round much
36:06 faster in the next video let's talk about the efficiency of binary search [Music] we have a vague understanding that britney's approach is better in most cases but just like with linear search it helps to visualize this much like we did with linear search when determining the efficiency of an algorithm and remember we're still only looking at efficiency in terms of time time complexity as it's called we always want to evaluate how the algorithm performs in the worst case scenario now you might be thinking well that doesn't seem fair because given a series of data if the target value we're searching for is somewhere near the front of the list then linear search may perform just as well if not slightly better than binary
36:52 search and that is totally true remember a crucial part of learning algorithms is understanding what works better in a given context when measuring efficiency though we always use the worst case scenarios as a benchmark because remember it can never perform worse than the worst case let's plot these values on the graph we started earlier with the number of tris or the runtime of the algorithm on the y axis and the maximum number of values in the series or n on the horizontal axis to represent the worst case scenario we have two data points when n equals 10 britney took four tries using binary search and when n equals 100 it took seven tries but even side by side these data points are sort of meaningless
37:38 remember that while there is quite a difference between the run time of linear search and binary search at an n value of 100 for a computer that shouldn't matter what we should check out is how the algorithm performs at levels of n that might actually slow a computer down as n grows larger and larger how do these algorithms compare to one another let's add that to the graph okay now a picture starts to emerge as n gets really large the performance of these two algorithms differs significantly the difference is kind of staggering actually even with the simple game we saw that binary search was better but now we have a much more complete idea of how much better for example when n is 1000 the runtime
38:24 of linear search measured by the number of operations or turns is also 1000. for binary search it takes just 10 operations now let's look at what happens when we increase n by factor of 10 at 10 000 linear search takes 10 000 operations while binary search takes 14 operations and increased by a factor of 10 in binary search only needs four more operations to find a value if we increase it again by a factor of 10 once more to an n value of 100 000 binary search takes only 17 operations it is blazing fast what we've done here is plotted on a graph how the algorithm performs as the input set it is working on increases
39:10 in other words we've plotted the growth rate of the algorithm also known as the order of growth different algorithms grow at different rates and by evaluating their growth rates we get a much better picture of their performance because we know how the algorithm will hold up as n grows larger this is so important in fact it is the standard way of evaluating an algorithm and brings us to a concept called big o you might have heard this word thrown about and if you found it confusing don't worry we've already built up a definition in the past few videos we just need to bring it all together let's start with a common statement you'll see in studies on algorithms big o is a theoretical definition of the complexity of an algorithm as a function
39:57 of the size wow what a mouthful this sounds really intimidating but it's really not let's break it down big o is a notation used to describe complexity and what i mean by notation is that it simplifies everything we've talked about down into a single variable an example of complexity written in terms of big o looks like this as you can see it starts with an uppercase letter o that's why we call it big o it's literally a big o the o comes from order of magnitude of complexity so that's where we get the big o from now complexity here refers to the exercise we've been carrying out in measuring efficiency if it takes brittany 4 tries when n is 10
40:42 how long does the algorithm take when n is 10 million when we use big o for this the variable used which we'll get to distills that information down so that by reading the variable you get a big picture view without having to run through data points and graphs just like we did it's important to remember that complexity is relative when we evaluate the complexity of the binary search algorithm we're doing it relative to other search algorithms not all algorithms bigo is a useful notation for understanding both time and space complexity but only when comparing amongst algorithms that solve the same problem the last bit in that definition of big o is a function of the size and all this means is that big o measures complexity
41:29 as the input size grows because it's not important to understand how an algorithm performs in a single data set but in all possible data sets you will also see big o referred to as the upper bound of the algorithm and what that means is that big o measures how the algorithm performs in the worst case scenario so that's all big o is nothing special it's just a notation that condenses the data points and graphs that we've built up down to one variable okay so what do these variables look like for john's strategy linear search we say that it has a time complexity of big o and then n so that's again big o with an n inside parentheses for britney strategy binary search we say that it has a time complexity of big
42:15 o of log n that's big o with something called a log and an n inside parentheses now don't worry if you don't understand that we'll go into that in more detail later on in the course each of these has a special meaning but it helps to work through all of them to get a big picture view so over the next few videos let's examine what are called common complexities or common values of big o that you will run into and should internalize in our discussions of complexity we made one assumption that the algorithm as a whole had a single measure of complexity that isn't true and we'll get at how we arrive at these measures for the entire algorithm at the end of this exercise but each step in the algorithm has its own space and time complexity in linear search for example there are
43:01 multiple steps and the algorithm goes like this start at the beginning of the list or range of values compare the current value to the target if the current value is the target value that we're looking for we're done if it's not we'll move on sequentially to the next value in the list and repeat step two if we reach the end of the list then the target value is not in the list let's go back to step two for a second comparing the current value to the target does the size of the data set matter for this step when we're at step two we're already at that position in the list and all we're doing is reading the value to make a comparison reading the value is a single operation and if we were to plot it on a graph of runtime per operations against
43:46 n it looks like this a straight line that takes constant time regardless of the size of n since this takes the same amount of time in any given case we say that the run time is constant time it doesn't change in big o notation we represent this as big o with a 1 inside parentheses now when i first started learning all this i was really confused as to how to read this even if it was in my own head should i say big o of one when you see this written you're going to read this as constant time so reading a value in a list is a constant time operation this is the most ideal case when it comes to run times because input size does not matter and we know that regardless of the size of n the
44:32 algorithm runtime will remain the same the next step up in complexity so to speak is the situation we encountered with the binary search algorithm traditionally explaining the time complexity of binary search involves math i'm going to try to do it both with and without when we played the game using binary search we notice that with every turn we were able to discard half of the data but there's another pattern that emerges that we didn't explore let's say n equals 10. how long does it take to find an item at the 10th position of the list we can write this out so we go from 10 to 5 to 8 to 9 and then down to 10. here it takes us four tries to cut down the list to just one element and find
45:18 the value we're looking for let's double the value of n to 20 and see how long it takes for us to find an item at the 20th position so we start at 20 and then we pick 10 from there we go to 15 17 19 and finally 20. so here it takes us five tries okay let's double it again so that n is 40 and we try to find the item in the 40th position so when we start at 40 the first midpoint we're going to pick is 20 from there we go to 30 then 35 37 39 and then 40. notice that every time we double the value of n the number of operations it takes to reduce the list down to a single element only increases by 1. there's a mathematical relationship to
46:04 this pattern and it's called a logarithm of n you don't really have to know what logarithms truly are but i know that some of you like underlying explainers so i'll give you a quick one if you've taken algebra classes you may have learned about exponents here's a quick refresher 2 times 1 equals 2. now this can be written as 2 raised to the first power because it is our base case two times one is two now two times two is four this can be written as two raised to the second power because we're multiplying two twice first we multiply two times one then the result of that times 2. 2 times 2 times 2 is 8 and we can write this as 2 raised to the 3rd power because we're multiplying 2 3 times
46:51 in 2 raised to 2 and 2 raised to 3 the 2 and 3 there are called exponents and they define how the number grows with 2 raised to 3 we start with the base value and multiply itself 3 times the inverse of an exponent is called a logarithm so if i say log to the base 2 of 8 equals 3 i'm basically saying the opposite of an exponent instead of saying how many times do i have to multiply this value i'm asking how many times do i have to divide 8 by two to get the value one this takes three operations what about the result of log to the base two of sixteen that evaluates to four so why does any of this matter notice that this is sort of how binary
47:37 search works log to the base 2 of 16 is 4. if n was 16 how many triads does it take to get to that last element well we start in the middle at 8 that's too low so we move to 12 then we move to 14 then to 15 and then to 16 which is 5 tries or log to the base 2 of 16 plus 1. in general for a given value of n the number of tries it takes to find the worst case scenario is log of n plus one and because this pattern is overall a logarithmic pattern we say that the runtime of such algorithms is logarithmic if we plot these data points on our graph a logarithmic runtime looks like this
48:23 in big o notation we represent a logarithmic runtime as big o of log n which is written as big o with log n inside parentheses or even sometimes as l n n inside parentheses when you see this read it as logarithmic time as you can see on the graph as n grows really large the number of operations grows very slowly and eventually flattens out since this line is below the line for a linear runtime which we'll look at in a second you might often hear algorithms with logarithmic runtimes being called sublinear logarithmic or sub-linear runtimes are preferred to linear because they're more efficient but in practice linear search has its own set of advantages which
49:09 we'll take a look at in the next video next up let's look at the situation we encountered with the linear search algorithm we saw that in the worst case scenario whatever the value of n was john took exactly that many tries to find the answer as in linear search when the number of operations to determine the result in the worst case scenario is at most the same as n we say that the algorithm runs in linear time we represent this as big o of n now you can read that as big o of n like i just said or you can say linear time which is more common when we put that up on a graph against constant time and logarithmic time we get a line that looks like this any algorithm that sequentially reads
49:55 the input will have linear time so remember anytime you know a problem involves reading every item in a list that means a linear run time as you saw from the game we played brittany's strategy using binary search was clearly better and we can see that on the graph so if we had the option why would we use linear search which runs in linear time remember that binary search had a precondition the input set had to be sorted while we won't be looking at sorting algorithms in this course as you learn more about algorithms you'll find that sorting algorithms have varying complexities themselves just like search does so we have to do additional work prior to using binary search for this reason in practice linear search ends up being more performant up
50:42 to a certain value of n because the combination of sorting first and then searching using binary search adds up the next common complexity you will hear about is when an algorithm runs in quadratic time if the word quadratic sounds familiar to you it's because you might have heard about it in math class quadratic is a word that means an operation raised to the second power or when something is squared let's say you and your friends are playing a tower defense game and to start it off you're going to draw a map of the terrain this map is going to be a grid and you pick a random number to determine how large this grid is let's set n the size of the grid to four next you need to come up with a list of coordinates so you can place towers and
51:28 enemies and stuff on this map so how would we do this if we start out horizontally we'd have coordinate points that go 1 1 1 2 1 3 and 1 4. then you go up one level vertically and we have points 2 1 2 2 2 3 and 2 4. go up one more and you have the points 3 1 3 2 3 3 and 3 4 and on that last row you have the points 4 1 4 2 4 3 and 4 4. notice that we have a pattern here for each row we take the value and then create a point by adding to that every column value the range of values go from 1 to the value of n so we can generally think of it this way for the range of values from 1 to n for each value in that range we create a
52:16 point by combining that value with the range of values from 1 to n again doing it this way for each value in the range of 1 to n we create an n number of values and we end up with 16 points which is also n times n or n squared this is an algorithm with a quadratic runtime because for any given value of n we carry out n squared number of operations now i picked a relatively easy so to speak example here because in english at least we often denote map sizes by height times width so we would call this a 4 by 4 grid which is just another way of saying 4 squared or n squared in big o notation we would write this as big o of n squared or say that this is
53:03 an algorithm with a quadratic runtime many search algorithms have a worst case quadratic runtime which you'll learn about soon now in addition to quadratic runtimes you may also run into cubic runtimes as you encounter different algorithms in such an algorithm for a given value of n the algorithm executes n raised to the third power number of operations these aren't as common as quadratic algorithms though so we won't look at any examples but i think it's worth mentioning thrown up on our graph quadratic and cubic runtimes look like this so this is starting to look pretty expensive computationally as they say we can see here that for small changes in n there's a pretty significant change in the number of operations that we need to carry out
53:50 the next worst case runtime we're going to look at is one that's called quasi-linear and a sort of easier to understand for lack of better word by starting with the big o notation quasi-linear runtimes are written out as big o of n times log n we learned what log n was right a logarithmic runtime whereas n grew the number of operations only increased by a small factor with a quasi-linear runtime what we're saying is that for every value of n we're going to execute a log n number of operations hence the run time of n times log n so you saw earlier with the quadratic runtime that for each value of n we conducted n operations it's sort of the same in that as we go through the range of values in n we're executing login
54:37 operations in comparison to other runtimes a quasi-linear algorithm has a runtime that lies somewhere between a linear runtime and a quadratic runtime so where would we expect to see this kind of runtime in practical use well sorting algorithms is one place you will definitely see it merge sort for example is a sorting algorithm that has a worst case runtime of big o of n log n let's take a look at a quick example let's say we start off with a list of numbers that looks like this and we need to sort it merge sort starts by splitting this list into two lists down the middle it then takes each sub list and splits that in half down the middle again it keeps doing this until we end up with a list of just a single number
55:24 when we're down to single numbers we can do one sort operation and merge these sub-lists back in the opposite direction the first part of merge sort cuts those lists into sub-lists with half the numbers this is similar to binary search where each comparison operation cuts down the range to half the values you know the worst case runtime in binary search is log n so these splitting operations have the same runtime big o of log n or logarithmic but splitting into half isn't the only thing we need to do with merge sort we also need to carry out comparison operations so we can sort those values and if you look at each step of this algorithm we carry out an n number of comparison operations and that brings the worst case runtime of this algorithm
56:12 to n times log n also known as quasi linear don't worry if you didn't understand how merge sort works that wasn't the point of this demonstration we will be covering merge sorts soon in a future course the run times we've looked at so far are all called polynomial runtimes an algorithm is considered to have a polynomial runtime if for a given value of n its worst case runtime is in the form of n raised to the k power where k just means some value so it could be n squared where k equals 2 for a quadratic runtime n cubed for a cubic runtime and so on all of those are in the form of n raised to some power anything that is bounded by this and what i mean by that is if we had a hypothetical line on our graph of n
56:58 raised to the k power anything that falls under this graph is considered to have a polynomial runtime algorithms with an upper bound or a runtime with a big o value that is polynomial are considered efficient algorithms and are likely to be used in practice now the next class of runtimes that we're going to look at are a runtimes that we don't consider efficient and these are called exponential runtimes with these runtimes as n increases slightly the number of operations increases exponentially and as we'll see in a second these algorithms are far too expensive to be used an exponential runtime is an algorithm with a big o value of some number raised to the nth power
57:43 imagine that you wanted to break into a locker that had a padlock on it let's assume you forgot your code this lock takes a two digit code and the digit for the code ranges from zero to nine you start by setting the dials to zero and then with the first dial remaining on zero you change the second dial to one and try and open it if it doesn't work you set it to two then try again you would keep doing this and if you still haven't succeeded with the second dial set to 9 then you go back to that first dial set it to 1 and start the second dial over the range of values you'd have to go through is 0 0 to 9 9 which is 100 values this can be generalized as 10 to the second power since there are 10 values on each dial raised to two dials
58:31 searching through each individual value until you stumble on the right one is a strategy called brute force and brute force algorithms have exponential run times here there are two dials so n is 2 and each dial has 10 values so again we can generalize this algorithm as 10 raised to n where n represents the number of dials the reason that this algorithm is so inefficient is because with just one more dial on the lock the number of operations increases significantly with three dials the number of combinations in the worst case scenario where the correct code is the last digit in the range is 10 raised to 3 or 1 000 values with an additional wheel it becomes 10 raised to 4 or 10 000 values as n increases the number of operations
59:18 increases exponentially to a point where it's unsolvable in a realistic amount of time now you might think well any computer can crack a four digit numerical lock and that's true because n here is sufficiently small but this is the same principle that we use for passwords in a typical password field implemented well users are allowed to use letters of the english alphabet so up to 26 characters numbers from 0 to 9 and a set of special characters of which there can be around 33 so typically that means each character in a password can be one out of 69 values this means that for a one character password it takes 69 to the nth power so 1 which equals 69 operations in the
1:00:05 worst case scenario to figure out the password just increasing n to 2 increases the number of operations needed to guess the password to 69 squared or 4761 operations now usually on a secure website there isn't really a limit but in general passwords are limited to around 20 characters in length with each character being a possible 69 values and there being 20 characters the number of operations needed to guess the password in the worst case scenario is 69 raised to the 20th power or approximately 6 followed by 36 zeros number of operations an intel cpu with five cores can carry out roughly about 65 000 million
1:00:52 instructions per second that's a funny number i know to crack our 20-digit passcode in this very simplistic model it would take this intel cpu to race to 20th power years to brute force the password so while this algorithm would eventually produce a result it is so inefficient that it's pointless this is one of the reasons why people recommend you have longer passwords since brute forcing is exponential in the worst case each character you add increases the number of combinations by an exponent the next class of exponential algorithms is best highlighted by a popular problem known as the traveling salesman the problem statement goes like this given a list of cities and the distance
1:01:38 between each pair of cities what is the shortest possible route that visits each city and then returns to the origin city this seems like a simple question but let's start with a simple case three cities a b and c to figure out what the shortest route is we need to come up with all the possible routes with three cities we have six routes in theory at least some of these routes can be discarded because abc is the same as c b a but in the opposite direction but as we do know sometimes going from a to c through b may go through a different route than c to a through b so we'll stick to the six routes and from there we could determine the shortest no big deal now if we increase this to four cities we jump to 24 combinations
1:02:24 the mathematical relationship that defines this is called a factorial and is written out as n followed by an exclamation point factorials are basically n times n minus one repeated until you reach the number one so for example the factorial of three is three times two times one which is six which is the number of combinations we came up with for three cities the factorial of four is four times three times two times one or 24 which is the number of combinations we arrived at with four cities in solving the traveling salesman problem the most efficient algorithm will have a factorial runtime or a combinatorial runtime as it's also called at low values of n algorithms with a
1:03:11 factorial runtime may be used but with an n value of say 200 it would take longer than humans have been alive to solve the problem for sake of completeness let's plot a combinatorial runtime on our graph so that we can compare an algorithm such as one that solves the traveling salesman problem as a worst case run time of big o of n factorial studying exponential runtimes like this are useful for two reasons first in studying how to make such algorithms efficient we develop strategies that are useful across the board and can potentially be used to make existing algorithms even more efficient second it's important to be aware of problems that take a long time to solve knowing right off the bat that a problem
1:03:56 is somewhat unsolvable in a realistic time means you can focus your efforts on other aspects of the problem as beginners though we're going to steer clear of all this and focus our efforts on algorithms with polynomial runtimes since we're much more likely to work with and learn about such algorithms now that we know some of the common complexities in the next video let's talk about how we determine the complexity of an algorithm because there are some nuances over the last few videos we took a look at common complexities that we would encounter in studying algorithms but the question remains how do we determine what the worst case complexity of an algorithm is earlier i mentioned that even though we say that an algorithm has a particular upper bound or worst case runtime each
1:04:43 step in a given algorithm can have different run times let's bring up the steps for binary search again assuming the list is sorted the first step is to determine the middle position of the list in general this is going to be a constant time operation many programming languages hold on to information about the size of the list so we don't actually need to walk through the list to determine the size now if we didn't have information about the size of the list we would need to walk through counting each item one by one until we reached the end of the list and this is a linear time operation but realistically this is a big o of 1 or constant time step 2 is to compare the element in the
1:05:28 middle position to the target element we can assume that in most modern programming languages this is also a constant time operation because the documentation for the language tells us it is step 3 is our success case and the algorithm ends this is our best case and so far we have only incurred two constant time operations so we would say that the best case run
…
