Now let's practice what we learned and dive into some other algorithms. For this I'll add a new file
alg-2 and here a one to write algorithm that allows us to find out if a number is even or odd,
so evenodd.js sounds like a good name to me
and let me import this here, alg-2-evenodd.js is imported and now in here the goal is that we have
a function, isEvenOrOdd
which takes a number, so not an array but a single number which of course is also something we can do
and I want to call this isEvenOrOdd with 10 for example and for 10, I want to get even as a
result
and on the other hand if I call this with let's say 11, I of course want to get odd as a result.
That's the goal,
so that is the input 10 and 11 and for this algorithm, the desired output then is even and odd.
How can we implement this?
Well for this, we can get a result by dividing our number with the modulus operator by 2 and this
will give us the remainder of the division,
so for an even number, the remainder will be zero
and for an odd number the remainder will be not zero.
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
return even here,
even like this, else we know we can return odd.
So this is how this algorithm could look like. If we now save this, you see I get even
and that was for this line where I passed in 10 and I get odd for the line where I passed in 11.
So this algorithm seems to do the trick.
Now we could also shorten this a bit and write it in one line if we wanted to with a ternary expression
where I check number divided by 2 with this modulus operator,
if that is truthy,
so if that is anything but zero, we return odd,
if it is falsy, so if it is 0, we return even. Keep in mind that 0 is treated as a falsy value,
so we have to return even here for the zero, for the falsy case and if we do that and we save this, we
would get the same output as before.
So that's an algorithm, which time complexity does this algorithm have?
Now you might think that it matters how we implement it
but that's actually not the case,
let's see how many dynamic segments we have,
so code where the amount of executions depends on the number we pass in and here the thing is, no matter
if you pass in 1, 10 or one million as a number, our code always runs exactly once.
There is no loop in there,
there is no recursion in there,
so there really is no code that would run multiple times no matter which number we pass in.
So actually here, we say that this has a constant time complexity or maybe let me put it below that function
to be in line with the other code files and a constant time complexity is expressed as Big O of 1.
So this means the input really does not matter,
this always has exactly the same execution time, no matter which number we feed in.
Now one word of caution here though, it's the case for this algorithm but it's not always the
case that an algorithm or a function with exactly one line as we have it here has a constant execution
time and I will come back to a case where this would not be the case later. So for now let's just accept
it like this and let's move on and let's add a new file, alg-3 and there I'll add an array
sum algorithm. So I'll name the file array sum and import it here, alg-3-array-sum.js and in there,
my goal is that I have an array of let's say numbers 1, 2 and 3, the numbers don't matter,
the order also does not matter and I want to be able to console log the result of a function call, sumUp
or whatever you want to call it where I pass in the array and this should then give me the sum
of the items
in the array, so the sum of the numbers in the array here.
So here I would want to get back 6 as a result for this example array. So for that, let's add this sumUp
array here and let's accept some numbers here,
you can of course name the parameter however you want and let's build a sum.
So maybe let's start at zero here and return the sum in the end and now we have to do something
here
and how do we sum this up?
Well one way would be to again add a loop where we start at i set equal to zero, where we go through
the entire array with this exact condition and increment i after each iteration and then our sum is
simply the old sum plus numbers i,
so we add the number we're currently looking at for each index here to the sum and then we return
the sum in the end
and therefore now if we save that and we reload, indeed I do get six here and if we try out a different
array, let's say with five here at the end, then my expectation would be to get eight,
if we do this, I do get eight.
So this is of course again a fairly trivial algorithm
but let's see what's its time complexity because you really need to be able to calculate this. Well we
get two constant parts here,
this first one where we initialize the sum and where we return the sum,
this executes once no matter how many items are in the numbers array. Well and then we got a loop which
goes through the entire array,
so of course since we go through the entire array, this here executes n times, n is the length of
our array and we go through the entire array.
So the time complexity here would be linear expressed as o(n),
so the longer our array is the longer, this function will take and it will grow in a linear way,
so 1000 items in the array take roughly 1000 times as long as a single item and with that, you're hopefully
getting a feeling for these time complexities.
So let me quickly go through some of the most important ones,
for example constant time complexity which we just saw,
another example for this would be pushing an item to an array and I will come back to arrays and data structures
in the next lecture by the way.
If we push an item onto an array, we append a new item at the end,
so the other items are not affected by this and therefore this also would have a constant time complexity.
No matter how many items are in the array in this example here,
this operation will always take equally long and it was the same for our isEvenOrOdd function, no
matter which number we checked, the operation time was always the same.
Now we also learned about linear time complexity, expressed with O(n) for example sumUp which we just
created. This here will take a linear amount of time,
the more items we feed in, the longer it takes but it grows in a linear fashion,
1000 items take 1000 times longer than a single item.
We also learned about quadratic time complexity where this would not be the case,
we express it with O(n^2) and here for example we could write our own sort algorithm which basically
uses the sorting logic
we wrote a little bit earlier in this module, where we have nested for loops, if we have a for loop in
a for loop,
we typically have quadratic time complexity. So that means the more items we have, the longer it takes
but this grows exponentially so to say, so it's not growing in a linear way but instead at a faster rate.
Now
needless to say that of course if possible, you want to avoid quadratic time complexity because you'll
quickly reach a point where operations take super long or might not be solvable at all. Now there also
is another complexity which we haven't seen thus far and that would be logarithmic time complexity, expressed
with O(log n) and here for example that would be a so-called binary search algorithm which we could implement
and there essentially what happens is that the more items we have, the longer it takes but it does
grow at a slow rate, slower than linear time complexity for example,
so for a million items, we don't take a million times longer than for a single item.
Now this is a time complexity we haven't seen an example for and there are other time complexities as
well.
There is a great article, not written by me but very helpful which you also find attached in the last
lecture of this module where you learn more about the algorithms and time complexity in general and
where you also see examples for different time complexities, different algorithms you can check out to
see for example such a binary search algorithm for logarithmic time and so on.
This is something I would recommend as your next step when you want to dive into this topic deeper because
this is a great place to learn about different algorithms, different time complexities and how to calculate
them and how to think about them,
so this is a strong recommendation that you check out this article.
Now with that however, I want to leave the algorithms for now and instead focus on data structures because
that's also in the title of this module and thus far, we haven't had a closer look at those.