1 00:00:02,250 --> 00:00:08,520 Now let's practice what we learned and dive into some other algorithms. For this I'll add a new file 2 00:00:08,610 --> 00:00:15,980 alg-2 and here a one to write algorithm that allows us to find out if a number is even or odd, 3 00:00:15,990 --> 00:00:19,150 so evenodd.js sounds like a good name to me 4 00:00:19,560 --> 00:00:29,380 and let me import this here, alg-2-evenodd.js is imported and now in here the goal is that we have 5 00:00:29,380 --> 00:00:33,230 a function, isEvenOrOdd 6 00:00:33,260 --> 00:00:39,860 which takes a number, so not an array but a single number which of course is also something we can do 7 00:00:40,100 --> 00:00:51,000 and I want to call this isEvenOrOdd with 10 for example and for 10, I want to get even as a 8 00:00:51,000 --> 00:00:51,600 result 9 00:00:52,170 --> 00:00:58,700 and on the other hand if I call this with let's say 11, I of course want to get odd as a result. 10 00:00:58,860 --> 00:00:59,700 That's the goal, 11 00:00:59,700 --> 00:01:06,920 so that is the input 10 and 11 and for this algorithm, the desired output then is even and odd. 12 00:01:07,050 --> 00:01:08,690 How can we implement this? 13 00:01:08,940 --> 00:01:18,690 Well for this, we can get a result by dividing our number with the modulus operator by 2 and this 14 00:01:18,690 --> 00:01:20,840 will give us the remainder of the division, 15 00:01:20,850 --> 00:01:24,570 so for an even number, the remainder will be zero 16 00:01:24,840 --> 00:01:29,680 and for an odd number the remainder will be not zero. 17 00:01:29,730 --> 00:01:36,180 So we can check if result is equal to zero and if that's the case, we know it's even, so then we can 18 00:01:36,180 --> 00:01:38,950 return even here, 19 00:01:39,060 --> 00:01:44,790 even like this, else we know we can return odd. 20 00:01:44,790 --> 00:01:51,700 So this is how this algorithm could look like. If we now save this, you see I get even 21 00:01:52,040 --> 00:01:58,660 and that was for this line where I passed in 10 and I get odd for the line where I passed in 11. 22 00:01:58,790 --> 00:02:01,450 So this algorithm seems to do the trick. 23 00:02:02,500 --> 00:02:08,230 Now we could also shorten this a bit and write it in one line if we wanted to with a ternary expression 24 00:02:08,380 --> 00:02:13,420 where I check number divided by 2 with this modulus operator, 25 00:02:13,570 --> 00:02:15,960 if that is truthy, 26 00:02:16,180 --> 00:02:20,910 so if that is anything but zero, we return odd, 27 00:02:21,160 --> 00:02:28,480 if it is falsy, so if it is 0, we return even. Keep in mind that 0 is treated as a falsy value, 28 00:02:28,600 --> 00:02:36,110 so we have to return even here for the zero, for the falsy case and if we do that and we save this, we 29 00:02:36,110 --> 00:02:38,820 would get the same output as before. 30 00:02:38,870 --> 00:02:45,520 So that's an algorithm, which time complexity does this algorithm have? 31 00:02:45,750 --> 00:02:48,410 Now you might think that it matters how we implement it 32 00:02:48,420 --> 00:02:50,460 but that's actually not the case, 33 00:02:50,490 --> 00:02:52,710 let's see how many dynamic segments we have, 34 00:02:52,710 --> 00:02:59,700 so code where the amount of executions depends on the number we pass in and here the thing is, no matter 35 00:02:59,700 --> 00:03:07,080 if you pass in 1, 10 or one million as a number, our code always runs exactly once. 36 00:03:07,110 --> 00:03:08,830 There is no loop in there, 37 00:03:08,880 --> 00:03:10,700 there is no recursion in there, 38 00:03:10,770 --> 00:03:16,220 so there really is no code that would run multiple times no matter which number we pass in. 39 00:03:16,230 --> 00:03:25,350 So actually here, we say that this has a constant time complexity or maybe let me put it below that function 40 00:03:25,350 --> 00:03:32,730 to be in line with the other code files and a constant time complexity is expressed as Big O of 1. 41 00:03:32,730 --> 00:03:35,440 So this means the input really does not matter, 42 00:03:35,460 --> 00:03:40,430 this always has exactly the same execution time, no matter which number we feed in. 43 00:03:40,430 --> 00:03:46,890 Now one word of caution here though, it's the case for this algorithm but it's not always the 44 00:03:46,890 --> 00:03:53,580 case that an algorithm or a function with exactly one line as we have it here has a constant execution 45 00:03:53,580 --> 00:04:00,440 time and I will come back to a case where this would not be the case later. So for now let's just accept 46 00:04:00,440 --> 00:04:07,320 it like this and let's move on and let's add a new file, alg-3 and there I'll add an array 47 00:04:07,350 --> 00:04:17,250 sum algorithm. So I'll name the file array sum and import it here, alg-3-array-sum.js and in there, 48 00:04:17,280 --> 00:04:24,120 my goal is that I have an array of let's say numbers 1, 2 and 3, the numbers don't matter, 49 00:04:24,130 --> 00:04:31,140 the order also does not matter and I want to be able to console log the result of a function call, sumUp 50 00:04:31,170 --> 00:04:35,460 or whatever you want to call it where I pass in the array and this should then give me the sum 51 00:04:35,550 --> 00:04:36,700 of the items 52 00:04:36,760 --> 00:04:40,060 in the array, so the sum of the numbers in the array here. 53 00:04:40,080 --> 00:04:47,450 So here I would want to get back 6 as a result for this example array. So for that, let's add this sumUp 54 00:04:47,480 --> 00:04:51,980 array here and let's accept some numbers here, 55 00:04:51,980 --> 00:04:57,240 you can of course name the parameter however you want and let's build a sum. 56 00:04:57,470 --> 00:05:03,980 So maybe let's start at zero here and return the sum in the end and now we have to do something 57 00:05:03,980 --> 00:05:04,520 here 58 00:05:04,640 --> 00:05:06,310 and how do we sum this up? 59 00:05:06,530 --> 00:05:13,280 Well one way would be to again add a loop where we start at i set equal to zero, where we go through 60 00:05:13,280 --> 00:05:20,150 the entire array with this exact condition and increment i after each iteration and then our sum is 61 00:05:20,150 --> 00:05:24,270 simply the old sum plus numbers i, 62 00:05:24,350 --> 00:05:29,780 so we add the number we're currently looking at for each index here to the sum and then we return 63 00:05:29,780 --> 00:05:31,340 the sum in the end 64 00:05:31,510 --> 00:05:39,530 and therefore now if we save that and we reload, indeed I do get six here and if we try out a different 65 00:05:39,530 --> 00:05:44,700 array, let's say with five here at the end, then my expectation would be to get eight, 66 00:05:44,720 --> 00:05:47,530 if we do this, I do get eight. 67 00:05:47,660 --> 00:05:51,290 So this is of course again a fairly trivial algorithm 68 00:05:51,290 --> 00:05:58,260 but let's see what's its time complexity because you really need to be able to calculate this. Well we 69 00:05:58,260 --> 00:06:00,240 get two constant parts here, 70 00:06:00,300 --> 00:06:04,020 this first one where we initialize the sum and where we return the sum, 71 00:06:04,050 --> 00:06:11,640 this executes once no matter how many items are in the numbers array. Well and then we got a loop which 72 00:06:11,640 --> 00:06:13,500 goes through the entire array, 73 00:06:13,500 --> 00:06:20,280 so of course since we go through the entire array, this here executes n times, n is the length of 74 00:06:20,310 --> 00:06:23,040 our array and we go through the entire array. 75 00:06:23,280 --> 00:06:30,450 So the time complexity here would be linear expressed as o(n), 76 00:06:30,780 --> 00:06:38,820 so the longer our array is the longer, this function will take and it will grow in a linear way, 77 00:06:38,820 --> 00:06:47,670 so 1000 items in the array take roughly 1000 times as long as a single item and with that, you're hopefully 78 00:06:47,670 --> 00:06:50,460 getting a feeling for these time complexities. 79 00:06:50,460 --> 00:06:53,820 So let me quickly go through some of the most important ones, 80 00:06:53,970 --> 00:06:57,200 for example constant time complexity which we just saw, 81 00:06:57,690 --> 00:07:03,330 another example for this would be pushing an item to an array and I will come back to arrays and data structures 82 00:07:03,330 --> 00:07:04,580 in the next lecture by the way. 83 00:07:05,070 --> 00:07:09,030 If we push an item onto an array, we append a new item at the end, 84 00:07:09,060 --> 00:07:14,520 so the other items are not affected by this and therefore this also would have a constant time complexity. 85 00:07:14,850 --> 00:07:19,170 No matter how many items are in the array in this example here, 86 00:07:19,290 --> 00:07:25,380 this operation will always take equally long and it was the same for our isEvenOrOdd function, no 87 00:07:25,380 --> 00:07:30,440 matter which number we checked, the operation time was always the same. 88 00:07:30,450 --> 00:07:37,350 Now we also learned about linear time complexity, expressed with O(n) for example sumUp which we just 89 00:07:37,350 --> 00:07:41,310 created. This here will take a linear amount of time, 90 00:07:41,340 --> 00:07:46,510 the more items we feed in, the longer it takes but it grows in a linear fashion, 91 00:07:46,530 --> 00:07:51,080 1000 items take 1000 times longer than a single item. 92 00:07:51,120 --> 00:07:55,940 We also learned about quadratic time complexity where this would not be the case, 93 00:07:56,010 --> 00:08:03,930 we express it with O(n^2) and here for example we could write our own sort algorithm which basically 94 00:08:03,930 --> 00:08:05,280 uses the sorting logic 95 00:08:05,280 --> 00:08:11,100 we wrote a little bit earlier in this module, where we have nested for loops, if we have a for loop in 96 00:08:11,100 --> 00:08:12,090 a for loop, 97 00:08:12,090 --> 00:08:19,530 we typically have quadratic time complexity. So that means the more items we have, the longer it takes 98 00:08:19,530 --> 00:08:27,390 but this grows exponentially so to say, so it's not growing in a linear way but instead at a faster rate. 99 00:08:27,780 --> 00:08:28,050 Now 100 00:08:28,050 --> 00:08:33,780 needless to say that of course if possible, you want to avoid quadratic time complexity because you'll 101 00:08:33,780 --> 00:08:40,830 quickly reach a point where operations take super long or might not be solvable at all. Now there also 102 00:08:40,830 --> 00:08:46,910 is another complexity which we haven't seen thus far and that would be logarithmic time complexity, expressed 103 00:08:46,920 --> 00:08:53,190 with O(log n) and here for example that would be a so-called binary search algorithm which we could implement 104 00:08:53,520 --> 00:08:59,220 and there essentially what happens is that the more items we have, the longer it takes but it does 105 00:08:59,280 --> 00:09:04,610 grow at a slow rate, slower than linear time complexity for example, 106 00:09:04,620 --> 00:09:09,720 so for a million items, we don't take a million times longer than for a single item. 107 00:09:09,930 --> 00:09:15,630 Now this is a time complexity we haven't seen an example for and there are other time complexities as 108 00:09:15,630 --> 00:09:16,840 well. 109 00:09:16,860 --> 00:09:23,580 There is a great article, not written by me but very helpful which you also find attached in the last 110 00:09:23,580 --> 00:09:30,120 lecture of this module where you learn more about the algorithms and time complexity in general and 111 00:09:30,120 --> 00:09:36,810 where you also see examples for different time complexities, different algorithms you can check out to 112 00:09:36,810 --> 00:09:42,210 see for example such a binary search algorithm for logarithmic time and so on. 113 00:09:42,240 --> 00:09:48,510 This is something I would recommend as your next step when you want to dive into this topic deeper because 114 00:09:48,540 --> 00:09:54,630 this is a great place to learn about different algorithms, different time complexities and how to calculate 115 00:09:54,630 --> 00:09:56,230 them and how to think about them, 116 00:09:56,250 --> 00:10:00,600 so this is a strong recommendation that you check out this article. 117 00:10:00,600 --> 00:10:07,920 Now with that however, I want to leave the algorithms for now and instead focus on data structures because 118 00:10:07,950 --> 00:10:12,990 that's also in the title of this module and thus far, we haven't had a closer look at those.