Coding

JavaScript Algorithms Crash Course – Learn Algorithms & “Big O” from the Ground Up!

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