Analyzing the algorithm.
So to create a good algorithm, we need to ensure that we have got the best performance from the algorithm.
In this lecture, we are going to discuss the ways we can analyze the time and complexity of basing
functions.
So my name is Stephan and let's get started.
So.
Uh, we're going to start with the asymptotic analysis.
So let's start with the simplistic analysis to find out the complexity of the algorithms.
So this analysis omits the constants and the least significant parts.
Suppose we have the function that will print a number from zero, from zero to N.
We're going to create a function like this.
So void, void, or actually, let's make this here, the void looping here.
We're going to get an parameter which is going to be n here and we will loop through it.
So integer, we're going to create a new integer E here.
We're going to assign it to zero.
Now we're going to create a while loop while E is less than n print on the screen with a c out E here,
end line.
And here.
We also need to input your string here.
Oops.
So include and include your stream, your stream.
And so we're going to print it on the screen and increment the E by one.
E equals E plus one.
So now let's calculate the time and complexity of the preceding algorithm by counting the each instruction
of the function here.
So this statement is only executed once in the function, so its value is one.
So this code snippet here of the of the rest statements in the looping function.
So the comparison while loop is valued at one.
And for simplicity we can say that the value of the two statements inside the while loop scope is three
signs.
It needs one to print the variable and two for assignment and addition here.
So however, how much of the this code is executed depends on the value of N here.
So it will be one here.
Let's actually make our mathematical here so it will be one plus three and multiply by N or for n here.
You can also do it like that.
So the total instruction.
Uh, that has to be executed for this looping function is one plus four.
N Therefore, the complexity of this looping function is here.
So the time complexity here.
The time.
Complexity.
Time.
Complexity.
Yeah.
Time.
Complexity.
And here time comes complexity.
N is equals for.
And plus one here.
So and there is let's actually create our curve here.
So in this case, it's our curve.
For example, let's just create a score here and this is our way, this goes here.
So it will be for N plus.
One.
So in our core graphics that will be represented in this course, the here, let's actually create this
again.
And this goes from here to here.
So for n plus one.
So this is the input axis.
The x axis here represent the input size N and the U here, the x axis here.
Let's actually write in red.
This is U here and this is X here.
So this axis here represents the execution time.
So here this means here.
This is the time.
So as you can see in this graphic, the curve is linear.
However, since the complexity is also depends on the other parameters such as hardware specification,
we may have another complexity for the preceding looping function if we run the function on a faster
hardware.
So let's say that complexity becomes two N, let's actually here, yeah, two N plus 0.5 so that the
curve curve will be like this.
So for example, this was the previous curve and this is the this is going to be our next curve here.
It's going to be like this.
So this is the four plus four N plus one, and this is the two N plus 0.5 here.
So it will be go down the time complexity if we have higher, faster hardware.
So as you can see, the curve is still linear for the two complexities.
For this reason, we can omit a constant and the least significant part is asymptotic analysis.
So we can say that this complexity is n here.
For example, the time complexity n here is equals to n.
Here.
So let's move another function.
If we have nested while loop.
So we will have another complexity here.
So looping while and void.
This is going to be my pairing here.
Pair pairing here.
And it's going to also get the integer n and we will create a new value named integer E here zero while
the e is less than n.
Then we're going to.
Could a new value.
The integer g here is zero.
And while the g g is less than n, we will print this on the screen.
So see out E here.
And also here and in line and line.
After that, we will equal G.
Equals G plus one.
And outside the our nested while loop in the first while loop here inside the first while loop we're
going to equal E equals e plus one.
E plus one.
Yeah.
So based on the looping function here, we can say that the complexity of the inner while loop of this
parent function is for n plus one.
So we then calculate the while loop.
So it becomes uh, here, uh, let's actually make this like that.
The one plus.
And multiply by four n plus one and plus two.
So which equals to one plus three N plus four N square here.
Square.
So therefore, the complexity of this preceding code is this.
Time complexity is going to be.
Here in this, as you can see here.
So here the time complexity instead of for n plus one, we're going to have the for the time complex
is going to be for n square here for n square plus three n plus one.
So and the curve of this preceding flow is going to be like this here.
This is our curve and it's going to be go from here and update like this.
Oops.
Actually, let's make the different color here.
Go from here and update like this.
So here, this is going to be for n for n two plus three, N plus one, and it's going to be this is
the time and this is the complexity here.
So and if the run if we run this code in the higher software, the complexity might become twice as
slow.
So and the notation is going to be, for example.
Eight and square.
Eight.
Yeah, the notation is going to be eight and square here.
Plus six and plus two.
It's conversation is going to be like this.
And the curve of notation is gonna like this.
So, for example, let's say this is our previous curve and this is going to be our next curve here
like this.
And this is going to eight N square plus six and that we've written here plus two here.
So.
And as shown here, signs the asymptotic analysis omits the constant and the least significant parts.
The complexity of the notation will be n two of our time complexity.