JavaScript Algorithms Crash Course - Learn Algorithms & "Big O" from the Ground Up!

now maybe you're in this course because you want to ace coding interviews and that would be totally fine though discourses for everyone who's interested in algorithms whatever your reasons might be but if we're briefly sticking to that interview situation you might get an interview question like this one you got a list of items where every item has a value and the weight and then you got a bag which has a maximum capacity a maximum weight it can hold off acts and that could be any number in kilograms anything like that so now your goal is to write a program that basically calculates the items that should go into the back to maximize the value of the items whilst of course ensuring that you don't exceed that maximum back weight so that capacity of the weight and here's an example with some numbers you might be getting or you might then derive on your own a list of items let's say ABC and of course that could be concrete items like bread and butter and whatever but here it's ABC and every item has a value and a weight and then we have this max weight let's say it's eight and our goal is to derive a bag and derive what should be in the back and in this very simple example here that would be the items a and C because combined they have a value of 13 and a weight of 6 so the weight is below that weight of 8 and the value is a pretty big one now we could have also just put item B into the back since that also has a weight of 8 so it would fit in but with Dad we would only get a value of 6 so dad wouldn't be the maximum now to us humans that's a pretty straightforward problem and we can solve this pretty quickly but if you would need to write a program if you would need to write code that solve said you would probably quickly reach a point where this becomes difficult now this task here is a very popular problem which is called the Kanab sac problem and it's often asked in interviews throughout the course we will solve it we're not at this point yet but we will solve it throughout the course but I already wanted to put it out there that's the key knapsack problem and we'll revisit it later now the question is why are companies asking for something like this it's probably not a problem you will need to solve when you work at Google or Facebook right there users don't pack bags well actually you might need to solve similar problems if you're responsible at Facebook for coding or for working on the part where users can create groups with a maximum number of participants and so on you might actually have similar problems but most importantly questions like this are asked to check your problem-solving skills because as a developer you need to be able to solve problems you're getting hired to solve problems and even if you're working on your own as a freelancer you are solving problems or if you're working on your own private projects or on your own startup you're also solving problems as a developer you're always solving problems and with that let's take a step back and have a look at the term algorithm what does this actually mean and why do we need algorithms now what is an algorithm an algorithm in simple words is just a sequence of steps of instructions you could say to solve a clearly defined problem this knapsack problem we would have to come up with code with an algorithm therefore which gets a clearly defined input which has the goal of solving a clearly defined problem maximizing the value and keeping that weight in mind and then you have to come up with steps that solve that problem and that's what an algorithm is about we have these two key parts a sequence of steps and a clearly defined problem and these are the two things that in the end make up an algorithm and the same steps with the same input should always lead to the same solution to a problem that's the idea behind an algorithm and therefore of course every program you're writing is an algorithm the entire code all code combined in a program is an algorithm and of course such programs can be split up in many smaller algorithms if you add a click listener to a button and on every click you add a number to another number you also have an algorithm there it's all an algorithm if you want to think of it like that and as a programmer as I mentioned your goal is to solve problems you need to be able to do that and of course you need to be able to do that efficiently which means for a given problem you want to find the best possible solution and of course there are different ways of defining the best possible solution and now of course the question is what is the best possible solution to a given problem is it the algorithm that has the minimum amount of code so the least amount of code is it the algorithm that takes the least amount of time to finish so that has the best performance is it the algorithm that uses the least amount of memory so that it doesn't take up a lot of resources on the computer or is it simply your personal preference because you like code snippet a better than code snippet B well of course we could discuss about that the best possible solution very much depends on the circumstances in which you're working but often it will be the best for Foreman's you're looking for that is typically what you would consider the best possible solution the algorithm with the best performance so that takes the least amount of time and with that the question of courses how do we measure performance because if we can't measure it we can't judge it now in order to find out what the best possible algorithm is for a given problem we need to be able to measure performance now let's see how we could measure it and for that let's take an example problem your goal is to write a function that takes one number as an input and then builds the sum of all the numbers leading up to that number this function could look like that it's a fairly trivial function we get a number as an input n and then we have a result 0 initially we have a for loop where we simply go through all the numbers up to n including n we add that to the result and we return the result in the end we can simply write this together here I'm simply doing this in the chrome developer tools in the JavaScript console there because for the moment that's all we need it's just a very basic first example for the rest of the course we will use code files no worries but here we could add a function sum up which takes n as a input curly braces opening and closing and between those hit shift enter to not submit it but to add more code in new lines and then here we have the result which initially is 0 shift enter add a for loop where we have I which is equal to 1 initially because we started ones we could include 0 but it makes no difference we want to go up all the way as long as I is smaller or equal to N and then we increment I curly braces and shift enter and then in there loop body we add I to result and then we in the end here return result this is the function that would solve this problem if we had entered we now submit this function and now it's stored here and we can use it so for example now we can call sum up for free and I get 6 as a result which makes sense because free is essentially free plus 2 plus 1 these are the numbers leading up to free and summed up they give us 6 and their first sum up for 4 gives us 10 because that's 4 plus 3 plus 2 plus 1 so this is the problem solved this is our first algorithm but how can we now matter the time it takes well for that I'll clear that it's still stored in memory I just clear the console so that we have more space for that we can measure the time when we start at the time when we end and simply take the difference for that I'll add a start variable which is 0 and end variable which is 0 initially and then here we can write start and in javascript in the browser there is a performance object on which we can call the now method and gives us the current timestamp now I can set start equal to that then call Sam up for let's say a value of five and then end is performance dot now and with that we can just output end minus start here in the console you can just type it like this and it will print the result and this will give us the amount of time this took to execute so if I hit enter here this is the result I get okay let's now repeat this for this you can press the up arrow key and let's say we use ten now instead of five if I hit enter you see I get pretty much the same time actually exactly the same time so it looks like it takes exactly the same time no matter what we enter here well let's confirm this by using let's say 1,000 as a value here if I now it enter oh okay I get a different time roughly three times as long as it took before right it was zero zero five before now it's zero one five so it's definitely not always the same time but it seems like there is no difference between five and ten well that's the problem with measuring time like this in hard numbers if we do this we have a lot of influencing factors that have nothing to do with our algorithm for example and easy to imagine the computer you are running this on matters I'm running this on a relatively new MacBook and of course that's a fast device on older devices you will see different numbers but even on this MacBook I don't always get the same result because it depends on how many processes are running in the background on the browser I use on the open tabs in the browser and on a lot of other things in addition the browser does certain optimizations behind the scenes where it caches my function and caches values so that even for one of the same value I will not consistently always get the same output so measuring time like this is not a great idea and especially for very small values like 5 and 10 it's very unreliable now still let's see it for some bigger numbers so instead of 1000 let's run it for 10,000 and now let's run it for 100,000 and let's run it for a million and be careful don't enter a too large number here because eventually it will freeze your computer but 1 million should work and you see we're getting results here now let's run it for 10 million that should still work and that will be the last number 100 million now we see a trend at least it tends to take longer for bigger numbers we have this strange result for 100,000 which took longer than 1 million but let's ignore that generally what we can roughly say is that the bigger the number the longer it takes and also roughly especially for the bigger numbers we can say that for 10 million which we have here it takes around 5 times as long as for 1 million for 100 million it takes 10 times as long as for 10 million now if I try this for a billion by adding one more 0 it gets stuck for quite some time but then again it's roughly 10 times the time it took for 100 million so it looks like 4 big numbers we roughly have factor 10 when it comes to the performance when we have factor 10 here on the number I use 1 billion instead of 100 million so that's 10 times 100 million I get 10 times the performance so this looks like the relation it looks like if we double the number for big numbers or we take it times 10 the performance is also doubled or taken times 10 and indeed this is how we should look at it we shouldn't care too much about the concrete numbers because those depend a lot on environment especially if we're working on small input numbers but we should care about the general trend especially for very large numbers so for this function if you would want to draw a graph for this for this function it would roughly look like this now we solve for small numbers it was very unreliable but for bigger numbers we saw a linear trend and theoretically that should be there for smaller numbers as well there we just had too many influence factors but generally we can say that for this algorithm a bigger number a bigger input number leads to more loop iterations and hence the time it takes to execute this function increases and for this specific function and therefore for this specific algorithm we saw that it seems to increase in a linear way especially for the bigger numbers we could see that if we take the number times 10 the time function takes also is essentially 10 times the time it took before so we have a linear growth function d R in the end the factor by which we increase the input so in this case n is the factor by which the time the function takes increases it increases in a linear way and that's how we judge performance when we talk about algorithms we don't care about the concrete numbers but we care about the trend you could say about the function of time so that we can basically make a statement about the performance of an algorithm based on the time it takes in relation to the inputs not speaking about absolute numbers but about this function about this trend this line and this chart here and we also call this time complexity so in this case we would say this sum up function and the algorithm in there has a linear time complexity now of course not all algorithms and JavaScript take linear time we saw this here this linear time function but we also sometimes have algorithms that take constant time so where the number of inputs has no influence on the time this algorithm takes and actually I can show you an example for constant time based on that example we just saw here I'm in a new tab and now I'm going to rewrite this sum up function in a different way because that's typical in programming often you have more than one way of solving a problem I mean if we wouldn't have alternative ways of solving a problem we wouldn't need to measure the performance right this entire idea of finding the best algorithm and of finding a way of comparing performance of algorithms well that entire idea would be useless and worthless if we only had one solution per problem but of course in programming you can be very creative and you can find dozens or hundreds of solutions for one and the same problem if you want you and that's why we need a way of comparing performance which is exactly what we're working on right now and here previously we solved this sum up problem with a loop well it turns out we can solve it in one line with a mathematical equation there is a pretty nice mathematical formula the dust is for us and it looks like this you divide n by 2 and then multiply the result of this with 1 plus n now this might look strange but this is just math and this is just a math formula which you can derive in mathematics that gives you in the end the sum of all the numbers up to a number I can prove that if I save that function if we call sum up for free I get 6 full 4 I get 10 4 5 I get 15 and 5 and 8 is 5 plus 4 plus 3 plus 2 plus 1 so this works and this just moth now here's one important difference to the solution from before here we have no loop we have one mathematical equation now if we try to measure this so if I now copy this measurement code here from before for a very large number you immediately see this is much faster and actually it doesn't change much no matter which number we use we just have this deviation based on the system we're running on now it even took zero milliseconds that's fast but generally you can see no matter which number I enter here it's super super fast and it doesn't really change we definitely don't have a trend as we had it before where large numbers led to a much longer execution time for the function now the execution time of this function is pretty much always the same because in there we have no iteration we have no loop we have just one mathematical term which is executed no matter which value we feed in for n and that is such an example for constant time the time it takes to execute the function is always the same no matter which value n has and this is not only an example for constant time this also shows us why it's important to know about time complexity and why it's important that you as developer are able to figure out which time complexity of function has because for this given problem of solving up all numbers up to n if you would have decided that this loop solution is the best possible solution you would have taken the slower algorithm we were able to find a faster one after all that's why measuring performance is so important and why you need to be able to write algorithms but why you then also need to be able to compare different alternatives to then find the best one now besides linear and constant time we also find algorithms that have quadratic time or even cubic time and a lot of other time complexities as well pretty much anything is possible here you can have all kinds of different graphs here that grow faster or slower but these are some of the common ones now we have one problem though I mentioned that we don't care too much about the concrete numbers we got for a good reason because they are influenced by a lot of factors now still we were able to identify some trend here we were able to identify that for the iteration solution with the loop for big numbers we have a linear relation between input and time it takes to execute the function and for our one-liner here we saw that the time doesn't really change a lot it certainly doesn't grow and as I mentioned that's important we care about the trend about the kind of function we have not about the concrete numbers and when we talk about the performance of an algorithm we therefore could say hey this solution has linear time complexity the other solution has constant time complexity but in programming we use something which is called Big O notation which simply makes it easier for us to quickly express the time complexity of a given algorithm to our developers and Big O notation looks like this for a linear time you write o of n for constant you have oo of one quadratic would be Oh N squared cubic would be Oh n with an exponent of free and you got other time complexities as well and you will see them throughout the course now we're using this because it's very easy to add this as an annotation in your code or to tell your interviewer that this solution has a complexity of oh of n so linear time complexity Big O notation is a super important concept you'll find it a lot in the internet and it's the standard way of comparing performance on algorithms you derived a Big O of an algorithm and then you know o of N is linear o of one is constant and you know constant is better than linear for example so this Big O notation plays a huge role and is super important when you're comparing algorithms now it's nice that we know about Big O Big O is great and we care about the function not about the concrete numbers now you just learned that for such a linear time complexity we would refer to know of n we would say this solution has a time complexity of oh of n which just means it has linear time complexity but the question is how can we derive this because the goal is not that you learn it by heart the goal of this course and that's important is not that you learn about a couple of algorithms and you memorize how to solve them and you memorize their time complexities the goal of this course is that by the end of the course you are able to come up with algorithms on your own and you're able to derive the time complexity on your own and of course you could always use an approach like we did before for logging the start and the end time and finding the difference and then you could try to find the relation now for a linear time complexity that's fairly easy but for our time complexities it's hard to see that relation since you always have to keep in mind that the time you see here is heavily influenced by a couple of other factors so you can't really rely on it to be very exact or correct and therefore you might accidentally see a linear relationship where you just have some distortion and you actually have a different time complexity so using these numbers in the browser is not how you should derive Big O and the time complexity the question then of course is how should you derive it for that we use a technique which is called asymptotic analysis and it involves three simple steps first of all for a given algorithm you define its function now here I mean the mathematical function you would write to get a graph as we have it on the left now of course that gives us a new problem though how do we define that function how do we know which function this JavaScript function so this code has the mathematical equation for that would be now one important note here I mean the mathematical equation of its time complexity so what would be the math function be for a graph as we have it on the right here which is produced by this JavaScript function how can we translate this javascript function into a math function that produces such a graph deriving the mathematical time complexity functions for JavaScript algorithms sounds scary but it isn't hard all you need to do in the end is you need to count the number of expression executions so with that I mean you look at your function at your algorithm and then you look at each expression so roughly speaking every line of code in it and you count how often that's getting executed now of course by counting this you will not get the real time in milliseconds or seconds this function will take but as I already mentioned earlier that's not what we're interested in anyways it's way too unreliable and influenced by too many aspects instead we simply assume that every expression in JavaScript takes roughly the same amount of time if we then count the number of expression executions so of code line executions we could say we can easily compare that number to the number of another alternative function that's the approach we're going to take here now we can't have a look at that for a couple of scenarios let's account for n equal to 1 n equal to 3 n equal to 10 and then let's see if we can detect a pattern for n equal to anything so 2 n for that I'll add some space here in the function because that makes annotating it a bit easier and now let's count and let's start with n equal to 1 how often does this first expression here execute where we initialize the result variable well I'd say for n equal to 1 this executes one time when this function does sum function execute this line here let result equal zero is executed exactly once now how often does this for loop initialization run and important I really mean the initialization of the for loop not the body well for n equal one this runs once we initialize this for loop once now what with the code inside of the loop how often does that run well if n is equal to one then we initialize I to one we run this loop or we run through that body in the loop as long as I is smaller or equal than one and if n is equal to one that means we execute the body in the loop exactly once because after that first loop iteration I will be incremented to 2 that of course is not smaller or equal than n which is 1 and therefore will leave the loop there after and now what about this last expression this of course also is only executed once once we make it out of the loop we run this line so that's the case for n equal to one every expression in this function runs once now what for n equal three what about that first expression here where we set the result equal to zero well this still only runs once it doesn't matter that n is equal to three when the sum up function runs this line only is reached once what about the loop initialization that also is only reached once we only execute this line of code once yes we will iterate through that loop a bit more but the loop initialization if we want to count it is only executes at once but what about the loop body now well this does now indeed execute three times because I is one initially we loop as long as I is smaller or equal than n and n is free which means we loop once then we increment I to two still smaller or equal then free so we loop a second time we increment I to that is still smaller or equal then free so we loop a third time and only then I is incremented to four which means we don't execute a loop again so that's now a difference and that last expression is still only executed once of course because once we're out of the loop we execute that line but thereafter the function is done we don't run anything else now for n equal to ten it's similar the first two expressions and the return statement are each only executed once but now the body inside of the loop is executed ten times and therefore you can of course see a pattern here for this algorithm we can say that the only dynamic part is the body in our loop and the times this body is executed is exactly the same number as we feed into this function here so therefore for n equal n the free expressions here are only executed once but the content in the loop the code in the loop is executed n times and with that we can now derive a function if we want to express the time complexity here with T then we could say for the case that n is equal to n which is of course the case we want to consider because the user is able to feed any number in then we could say the number of code executions we get for this function is 1 plus 1 plus n plus 1 now of course we can sum this up to 3 plus n and we could rewrite this as 3 plus 1 times n 1 x n simply because well just n is the same as 1 times n and you'll see in a second why I'm writing it like this this is in the end a mathematical function that would describe the number of code executions we have for this JavaScript function now it does not describe the absolute amount of milliseconds or a seconds this function takes but as I said that is hard to quantify anyways but if we assume that every line of code execution roughly takes the same amount of time you could say if we assume that then of course we can use such a equation to compare this algorithm to other algorithms however we don't even need to be that exact after all if you always count all code executions you have a slower algorithm just by adding an additional line of code in there right because we would have to count that and they offer we would have a different mathematical function because we added one extra line but of course the big picture wouldn't really be changed that's why we don't have to be that exact because we don't really care about the exact number of code executions as mentioned before we instead care about the general function the kind of function to be precise the trend to growth rate implied by that function so therefore when we define that function we don't need the exact function with the exact numbers instead we can generalize that and therefore we could also write a times n plus B I replaced the concrete numbers 1 and 3 with coefficients simply because the concrete numbers don't matter it's the big picture that matters to us here which kind of function is this and this is a linear function ok so now we got the general mathematical function and the worries will of course see this process of deriving the functions on for other algorithms in this course as well so we got this function now now in order to derive this Big O notation we need to find the fastest-growing term in that function and here it it's easy that is a times n because B is a constant coefficient which doesn't grow at all it's always exactly the same number a times n on the other hand depends on n and for a bigger n that term is bigger so now that we found this fastest-growing term we remove the coefficient from that term because again we don't care about the exact numbers we care about the general picture the big picture the general kind of function this process here is called asymptotic analysis now we narrowed this down basically dysfunction we can clearly see that the time complexity depends on n well and that n is simply what you put between the parentheses of the Big O notation that is why it's Big O of N so with our newly gained knowledge let's now use it to calculate the constant time complexity and see how all of one is derived so here's the sum up function with this one liner solution with this mathematical function and now again let's count the number of expression executions to find out how often that code runs so let's look at the N equal one case and let's evaluate that one code expression we got here how often does this run if n is equal to one well it runs once what about n equal free now you could think this runs three times because we use the number n in this mathematical calculation but that is not how Java Script and programming languages work if you have a loop or something like that then the code inside of the loop is of course affected by the number of iterations if you add two numbers let's say 100 and 100 this does not mean that JavaScript has to perform a certain execution 100 or 200 times behind the scenes and here n could simply be replaced with free so you would have 3/2 which is 1.5 times 3 plus 1 which is 4 and this does not mean that it runs 1.5 or 4 times now it still only runs exactly once so this expression here runs once for n equal to 3 and the same is true for n equal to 10 and for whatever value you have an N and therefore you can see if you write this as a function T equals 1 there is no N anywhere in this when we count the number of executions we got no expression that would run n times they one expression we got here runs once so if you would want to derive Big O here then we would to find a function well we did that it's T equals one and here of course there is no more general form because there is no N in it if we find the fastest-growing term that's of course one it's not growing at all but it's the only term we got and if we want to remove the coefficient there is nothing to remove so T equals one is our final time complexity function and as before we take what's left on the right side of the equal sign and put that between the parenthesis of our Big O notation hence you get o of 1 that's how we would derive constant time now just as before it is worth noting that it doesn't matter if you have any extra code lines in there right if we had another console.log statement here of course we would count Q executions so our formula would be 1 plus 1 every line runs once so we would end up with this equation what you would do in practice is you would simplify this so this does not lead to o to Big O of 2 but instead we would still write Big O of 1 because we care about the general trend that's why we focus on the fastest-growing term and remove the coefficient here when we have a linear growth function or when we have any time complexity function because we don't care about the exact number of code executions and different lines we want to see the general trend here it's linear time complexity so that T depends directly on n in a linear way and here it's oh one no matter if you add an extra line of code or not in the end what you want to say here in the constant time case is that the time a function takes to execute does not depend at all on n and constant times of course the best possible case for an algorithm because it means no matter what you put into an algorithm it will always deliver the same execution time it has a constant time complexity which is of course awesome and highly efficient but I can already tell you you will not be able to convert every algorithm to a constant time algorithm this specific algorithm we had a look at here is an exception where we have a linear and a constant time complexity alternative for a lot of problems you will not be able to find a constant time complexity alternative but we will see those algorithms throughout the course and will then of course also see different alternatives for those algorithms now just to make this really clear again we do derive these big o-notation x' to compare different algorithms because we can't rely on the hard numbers when we measure that when we measure it in milliseconds or seconds we can't rely on that that's what we have this Big O notation which tells us which kind of algorithm that is which kind of time function it has now we learn about constant time complexity and about linear time complexity thus far for constant time complexity n the number of inputs has no effect on the time the algorithm takes for linear time complexity the execution time grows guess what linearly with n so the bigger the n the longer the execution time and the factor should be the same so if you put 10 times as much n into the function it should take 10 times longer now therefore we can clearly say that o of n linear time complexity is worse than constant time complexity if we have a look at those charts we can see the same basically for oh of 1 we always have the same execution time no matter the inputs for o of n that's not the case so o n is worse than oh of 1 as I mentioned before though you don't always have the choice you can't always come up with a solution that has oo of 1 as you will also see in this course still that's how these two time complexities are related and in general here on this slide I will order these algorithms from fast to slow and therefore let's have a look at a couple of other time complexities you might see from time to time for example logarithmic time complexity which would be written like this o of log n graph could look something like this and we can see that here maybe initially it's slower than linear time complexity but with bigger ends it tends to be faster because it doesn't grow linearly it grows at a slower pace instead so the execution time of the function grows logarithmically with n 4 o N squared we speak of quadratic time complexity graph might look something like this and here the execution time grows quadratically with n so the bigger n the bigger the execution time and it grows much faster than for linear time complexity we have even faster growth and therefore an even slower algorithm with exponential time complexity so - at the power of n here this grows even faster than quadratic time complexity and therefore since execution time grows exponentially with n we have a very very very slow algorithm which will quickly be impossible to execute for very low ends you will already see problems here now this are not all possible time complexities we have in theory any mathematical function or construct is possible the most common ones are definitely linear constant and quadratic time complexity mixed with a bit of logarithmic time complexity and in general as I mentioned a couple of times already throughout this course we'll see plenty of examples also for different time complexities now however it's time for you to practice what you learned because it's nice if I explain all of that you really need to understand it you really need to become comfortable with coming up with solutions and judging their quality judging their time complexity this is something you need to learn now we will develop this throughout this course but I already got a nice first practice for you which you can absolutely solve with standard JavaScript skills and what you learned up to this point I want you to write an algorithm so write a function that takes an array of numbers as input and calculates the sum of those numbers then define the time complexity of that algorithm you came up with and check if there is a faster alternative so find out what the lowest possible time complexity so the fastest possible algorithm is for this problem so if we have a look at the code you should write some function some numbers which takes an array numbers as input and what you can call like you see here in the second line and you get back the response in this case 14 for summing up those numbers so your task is to write this part that's inside the function and determine the time complexity of your solution as well as the lowest possible time complexity you're able to come up with now for that attached you find a little starting project if you want to call it like this it's a very simple JavaScript project with a HTML file which is empty which just imports a JavaScript file which is also empty and that's where you should add and call your function outputting the result in the console of the developer tools is perfectly fine you don't need to do anything else the other files you see here are just for configuring git and for configuring my editor for recording so you just find the index.html and the app.js file attached you can use this as a starting project and add your solution in app trace and we'll solve it together in the next lecture were you successful let's solve it together now and for that I'll add a function some numbers which takes my numbers as parameter of course that parameter name is up to you and I want to call this with let's say an array where I have 1 3 and 10 and I want to console.log the result of the function so the function should simply return the sum now how could we sum this up if we knew that the array always has exactly 3 elements we could return numbers 0 plus numbers 1 plus numbers 2 that would be a valid solution if we knew that we always get exactly free elements now the problem is that is not something we know here when I gave you this exercise I didn't mention that it would be restricted to a certain length of number arrays so you can't assume this nonetheless if you could this would probably be the best possible solution because this has a time complexity of all of one so a constant time complexity simply because we have one expression here and for numbers which has free elements if we assume that it's always fixed to three elements this still only runs once so this here would be all of one constant time perfect unfortunately as I mentioned it's not something we can assume so I'll leave it here for reference but it's probably hopefully not a solution you came up with instead we don't know how long numbers is so let's add a result variable maybe which initially is zero and let's add a for loop to go through all numbers we're getting now numbers is an array here not a single number so we can use a for off loop to loop through that so for every number of numbers we execute the code inside of the loop now the code we execute in here is simply that we add a number to our result and then we return result thereafter this could be one solution for this problem if we now save this and we run this in the browser I get 14 which is the expected result now let's also try it with a different array where I also pass 50 as a 4th value and we should now get 64 as a result and that's the case so our function our algorithm seems to work the question now of course is which time complexity does it have and can we do better than that now let's derive the time complexity of this solution and for that let's count executions so let's count for a numbers being equal to an array with three elements if that's the case this first line runs once right it's only executed once when this some numbers function is called it does not depend on the length of numbers this loop here on the other end runs more often than that it runs three times now the loop initialization here actually is only done once but instead of the loop we run the code three times because we have three elements so our n here is the length of this array because that's what determines how often this code inside of the loop executes so that's our n now this last line still only runs once because it does not depend on the length of this array now if we have a look at this case with 50 as a fourth value this first line still only runs once this loop is only initialized once and this line where we return the result all the only runs once but of course now this code inside of the loop runs four times because we got four elements and that is what influences this code here and the number of iterations we have so if you would want to write this as a function here we would have one plus one so this code execution plus this code execution plus this code execution in the last line plus n in the end write plus four but if we consider an infinitely long array where we simply have a look at n elements this would be our dynamic part because this part here depends on the length of the array and that is our n in this case so we could write this as free plus N and as you learned that is free plus 1 times n if you want to write it like this so this year would be our time complexity function now you learned that as a first step we should then find the fastest-growing term and that definitely is this part here so we would simplify to that and then we would remove the coefficient so the 1 so we're left with T equal n now as a side note if you had an extra line in there where you can't so lock something you could of course count this extra line and this would execute four times as well but the only difference would be that you in the end would write plus n plus n right because you have two ends now basically so you have Q n here two times n hence you simplify this to two times n you remove the coefficient and you get the same result that's what I meant earlier it does not matter if you add an extra line it's about the general big picture so therefore we would write this as o of n and that of course is linear time complexity that's the time complexity we got here now the question is can we do better now generally that's of course not that easy to answer you probably don't know all possible solutions to all possible problems but let's dive into the code is there something we could improve now for that of course we should focus on the part of our code that depends on n because we can't improve this first line or this return statement it runs only once so there's no way of improving that but if we could get rid of that loop we will certainly win a lot but to be honest for this problem if we don't know the length of the array in advance there really isn't a way of getting rid of that loop there really isn't a way of shortening this here now of course you could get rid of that for loop you could get rid of that implementation we have here and you could instead return numbers reduce using the built-in reduce method that comes with JavaScript essentially where reduce takes a function for example an arrow function where you then get your sum and the current number you're looking at and you initialize the sum with zero with that second argument you pass to reduce and instead of that function you return sum plus Kurn um with that solution if I save that I still get 64 as a result and now we have a one-liner which is as we learned just Big O of one constant time so we won right it's better yeah not really this is something you could think and if that was your thought process I can't blame you but it's not entirely correct this year calls a new function right now before when I showed you that magic function for adding up all numbers we had one mathematical equation that was n divided by two times n plus 1 now we're not calling a function here we have a mathematical equation here which is solved by JavaScript here we are calling the reduce method and the reduce method internally will do something similar as we're doing here so reduce will not really turn this into a Big O of one solution because we make our function shorter by relying on an a verbal in function but that doesn't make the built-in function faster and that's an important takeaway just because you were able to shrink your code down to one line does not make it a constant time code that's only true if in that one line you're not calling a new function here we are calling a new function the reduced method so we would have to look into that reduce method and find out what its time complexity is to derive the time complexity of our function here now you could do that but in the end I can tell you reduce will also give us linear time complexity so this is not an improvement indeed this solution we had before where we have a simple loop where we go through all the elements that's our best possible solution in the end that has linear time complexity and for this problem we can't do better than that and that's what I also mentioned before you will not always be able to get a constant time algorithm sometimes you just have to live with linear time complex like in this case sometimes you have to live with the even worse time complexity so here it's linear time complexity and I hope I could make clear how we derive this and why it is the best solution here so now we already had a quite nice introduction into the basics of algorithms the very important topic of time complexity and therefore I now want to give you an overview of what's inside this quiz in general and what the course goal is because this course is not an algorithm practice book it's not full of hundreds of algorithms through which we're going to go but it isn't that because I find it much more important that you are put into the position that you're able to solve problems on your own you need to be able to come up with your own solutions with your own algorithms and this course has the goal of giving you a foundation for that therefore we'll of course thoroughly look at the what and why I already gave you an introduction to algorithms and throughout this course we'll always come back to this key question why are we doing something how does something work what is the approach here we'll see a bunch of examples just because this course isn't a practice book does not mean that we're not having a lot of examples we do but we'll see a lot of examples on different algorithms different kinds of algorithms and also very important different solution approaches so different ways of solving algorithms but although some repetition so that you have a chance of getting a feeling for a certain way of solving something so that you have a chance of understanding how to tackle certain problems we'll have a look at recursion at something which is called dynamic programming and greedy algorithms and more the overall goal of this course is to give you one cool thing a solid foundation and a plan on how to tackle and solve problems now I want to be very clear by the end of this course you will not be able to solve any problem that is out there in just five seconds this is not how it's going to work instead this course will lay out a foundation on which you can build up on to then practice on your own to dive into more algorithms and to understand what you're doing there so that finally after practicing and with help of this course you are able to solve problems to ace interviews and to do whatever your goal is I'm going to be very honest here because no course can just give you that knowledge you need to develop it on your own but for that you need a solid foundation and that is what this course will give you now in detail in this course we have all those basics and we learned about time complexity in this first module already and that is one of the most essential parts you need to know to get started with algorithms now of course getting started is nice and we need those essentials but we also want to apply them we want to dive into concrete examples therefore in the next module we'll explore math algorithms we'll explore algorithms that have something to do with numbers with mathematics and where you will already dive deeper into these core concepts and be able to utilize what you learned in this first module now as a next step thereafter I'll introduce a very important concept and that's recursion combined with dynamic programming you'll learn what's dynamic programming is and why it's extremely important when we're working with algorithms when we're tackling problems now with that new tool with that new knowledge gained will explore search algorithms and sorting algorithms two very important categories of algorithms which you'll need and real-life a lot and we'll thereafter explore a different metric besides time complexity which I can already say is the most important one but besides that will then also explore space complexity now with that and with all that new knowledge you gained throughout these modules will dive into sets and array algorithms sets essentially are arrays we could say here and you will learn how that all works and which tricky problems we might face there after dead we had a lot of practice we learned a lot of key concepts and will therefore then dive into more complex algorithms for example the problem outlined at the very beginning of this module I'll give you a blueprint a plan for solving problems and for deriving algorithms now what I've written note here though it might be tempting to just go ahead and dive into you that last section were just dive into the sorting algorithms section because maybe you just want to learn sorting algorithms this is not how this course works at least there might be other courses which simply are practice after practice after practice this course has a clear idea of building up a strong foundation that you have at the end of this course and therefore I strongly recommend that you go through the sections in order and if you do jump ahead be prepared to face concepts or solutions which you might not fully understand or where you need to do your own research so my strong recommendation is that you go through the sections in order and then by the end of the course you will have that strong foundation on which you can build upon if you enjoyed this video you might be interested in joining the complete JavaScript algorithms course you find a link below the video now in that course will dive way deeper into algorithms we'll have a look at math sorting and search algorithms will dive into array and set algorithms and we'll dive into more complex algorithms like the Kanab psych problem I showed at the beginning of this video now in addition we will not just see more examples I will also give you the tools to solve any algorithm or to solve any problem with the algorithm to be precise will dive into recursion and dynamic programming we'll have a look at greedy algorithms and by the end of the course you will get a plan but you can follow a step-by-step to find a solution for any problem so I would love to welcome you on board the course as I mentioned below the video you'll find a link otherwise I hopefully see you back in future videos on this channel

Channel: Academind

Views: 119,837

Rating: 4.9665203 out of 5

Keywords: javascript, algorithms, javascript algorithms, js algo, js algorithm, js algorithms, js big o, javascript big o, js time complexity, javascript time complexity, js knapsack, js knapsack problem, javascript knapsack, javascript algorithms course, full course, tutorial, js course, js tutorial, maximilian schwarzmuller, maximilian schwarzmueller, maximilian schwarzmüller

Id: JgWm6sQwS_I

Length: 61min 49sec (3709 seconds)

Published: Wed May 20 2020