When we have multiple available solutions for a given problem, we of course want to find the best one
and for this, we need to compare the solutions
but how do we compare different algorithms?
In the end, it typically comes down to the runtime performance.
We wonder how long does an operation take and of course, we want to pick the solution which takes the
less amount of time, so which is fastest to execute.
Now the problem just is, of course we could use a stopwatch and measure how long our different algorithms
take for different inputs but this would not really be a good idea,
it depends way too much on the hardware we're running on, which other processes might be running in the
background and for small data sets, for small amounts of data,
there might be a lot of variation. So indeed we try to measure and express this in a generalized form
and not in time units, not in seconds and so on because that would be really hard to measure,
instead we use something which is called time complexity and there, you could simply imagine a chart
where you have two axis and one is the time axis and one is the number of items or the size of the input
you're feeding into your algorithm and then you have a certain relation between the number of items
you're passing into your algorithm and the time it takes to execute and this is expressed with something
which is called the Big O notation, which we write like this.
Now that's very abstract, so let me explain what exactly this means, what the Big O notation is and how
we could measure this for our two example algorithms. Back to the two algorithms we wrote,
how long does this approach take and how long does this solution take?
Well let's start with getMin,
how can we find out how long it takes? For this, we in the end start by counting the number of executions
of the different parts of our algorithm, so you could say we count how often each line in this function
is reached for a given input.
Now let's say here, our input is 3, 1, 2,
so we're feeding in an array of three elements.
How often will this block execute then? Exactly once,
this is not inside of a loop,
this is just in the function itself,
we call that function once no matter how big our array is,
so this part here executes exactly once
so one execution and that's true for the entire if statement, so including the code which is inside
of the if statement, of course this part technically doesn't always execute, this will only execute if this condition
is true but therefore at most it executes once,
sometimes this line will not execute at all,
the if statement overall is executed once.
So what about this line here?
It's also outside of the for loop, so it also only executes once, we have one execution here because
this only gets executed once when the function gets called.
Well actually to be precise, of course if we would feed in an empty array or not an array at all
so that our first if statement catches this and throws an error,
this line and all the other code in this function would not execute at all.
So it's not always running once,
sometimes it doesn't run at all
but that would be different cases for this algorithm,
so in the best case from a performance perspective, we get invalid data and the algorithm doesn't run
once. That of course is great for performance, not so much for our application logic though. We typically
look at something which is called the average case though, which simply means on average we expect
valid data and therefore on average, this line of course will execute once,
so that's just important to understand how you work with these if statements. You can't participate
which concrete values you get,
you don't know the exact data you get,
so we simply take the common case, the typical case we would expect. Now the return statement here also
is executed once because we only return once in this entire function.
So now what about the for loop?
Well of course the loop itself so that we dive into it executes once but then the code in the loop executes
more often, so we could say this gets executed once,
this exact line but now inside of the loop,
of course we run more often.
What about this line here?
How often do we run this if check?
Well we have three items in the array but we start the loop at item two.
So this loop, for an array of three items, will run twice because it doesn't run for the very first item,
it starts at the second item.
So here we should have two executions of this line here and then in here,
this depends,
this depends on the concrete data we get.
It might never execute if we have an array as an input where the first element is the smallest because
then this condition will never be met but if we have an array where we have a smaller item after the
first element, then this will at least run once,
so this here could be anything between zero to two executions in our case here. For this concrete array,
we know this would execute once, it would execute once because for the second element which is the smallest
one,
this condition would be fulfilled and therefore we would run it,
so we have one execution here for our concrete example. Now in case this is not entirely clear,
you can of course also throw in some console log statements, for example here and there we could log
execution for and add a couple of other breakpoints, for example execution init and then here execution
return
and then you could of course simply count this.
So here you see execution init runs once, execution return runs once, execution for runs twice,
that's exactly what I wrote here, 2, 1, 1.
So that's also something you can do if you're not sure whether you counted correctly,
so here it looks like we did count correctly.
Now overall we can therefore also express this in mathematical terms you could say. We can group this
into three main blocks, the initialization block here because these lines here all run equally often,
then the part where we're done and then also the dynamic part here
and of course it depends on your algorithm,
how many different blocks of code you can identify.
So here I would say we have these three main blocks - initialization,
then our loop logic and then the return statement.
So if we want to derive the time and with that, I mean the number of executions, then we could say that
we have three blocks. We have one execution here for this first block and one execution for this last
block
and in between, we have two executions
and with that I don't mean the number of lines that get executed but simply how often these three blocks
get executed at most here.
Now why am I writing it like this?
Because if we take a closer look at this function here, we actually see that this block and this block
are executed in a constant way, which means these two blocks don't depend on the input size, on the number
of items in the array in this example,
no matter if we have an array with three items or with a million items, this will only run once,
this part here and this will also only run once.
So this is constant, so
we could have c1 and c3 here,
so the first and the third block are in the end constant,
so we don't care about the concrete values.
Now what about this for loop here?
Now here, the execution depends on the length of the array,
it's basically executing n-1 amount of times you could say. So for an array with three elements,
this runs twice, for an array with a million elements, this would run 990,999
times. Now since we initialize our current minimum with the first number in the array
here and therefore this also depends a bit on the array,
right,
this here also accesses our array,
we could therefore also simplify this as to just n and we could say this runs n * c2 times, what
is c2? c2 was our constant number of executions we have inside of the for loop, this here runs two
times but it only runs once per loop iteration you could say right, so this if loop is executed twice
because the for loop runs twice because we have an array of three elements but this if statement of course
only runs once per loop iteration.
So we have that constant value of 1 inside of the loop, for every loop iteration,
this code here happens to run once. So why am I doing it like this?
Because what hopefully gets obvious here is that the constants don't really matter to us,
it's not interesting whether we have some code that runs exactly once at the beginning and the end independent
from the input size, we want to measure how long this algorithm takes,
so how many operations it executes based on the number of items we feed into it.
So if here we feed in one million items and this line still only executes once, then this line is simply
not interesting for us,
this does not make the algorithm any better or worse,
instead what matters to us are the parts in the algorithm that depend on the input size because that
is what will scale up or down.
So here, we can simplify this to just n in the end because this loop
you could say combined with this line runs n times, if we feed in an array of three elements, this here
in the end goes through all the items in the array, so it runs three times you could say. Of course the
loop technically runs n-1 times but for a large array of a million items, the -1 really
is not interesting.
So this simply depends linearly on the length of the array,
so here we would say we have linear time complexity and we typically express this in this big O notation
which means we write a big O and then in brackets, the input size,
so n. So that simply means our algorithm here depends
in a linear way on the number of inputs. If we feed in more items, it will take longer but it grows in
a linear way,
so feeding in 1000 elements takes around 1000 times as long as it takes for one item.
It does not grow exponentially or slower,
it grows at a linear array, so the more items we feed in, the longer it will take but it will grow in a
linear way.
Now let's maybe have a look at the second approach here to see a different example, a different time
complexity and how this notation helps us compare algorithms.