Asymptotic Analysis (Solved Problem 1)

Here in this presentation will consider us solved problem one related to asymptotic analysis. So, let's get started. What is the time complexity of the following program? The program is available in front of you. You need to determine the time complexity of this particular program. Here you can see, this is not a complete program. Only a function is given in front of you. And let me tell you that, this function accepts one argument, that is value for n. And within this function we have these statements written over here. So, you can clearly see that the first statement is, I'm declaring three variables and one more variable and I have initialized this variable with value zero.

This is a count variable which is been initialized with value zero. Then we have these for loops which are basically nested for loops. And within this for loop have the statement, count plus plus. You need to determine the time complexity of this program. It would be better if you can pause the video for a while and try to answer this question on their own.

I hope you're done. Okay, let's move on to the solution. Now, let's take this statement first. Here you can see, I've declared three variables and one more variable count which has been initialized to zero. These three variables haven't been initialized. We will use these three variables within these for loops. You can see the time complexity in this case is big O of one because it's just taking a constant amount of time for the execution. You know, there are no for loops, nothing special. You can treat this as a single statement. Although, you can write these in multiple lines as well but we treat this as a single statement. If you treat them with different statements as well, then also it will take constant amount of time. Isn't that so? So, this particular statement just taking a constant amount of time.

Now, let's consider this particular statement. This is nothing but a for loop, right? Within this for loop we have another for loop. And within this for loop, we have another for loop. Then we have this statement. Obviously, our task is to find how many times this particular statement has been executed. So, let's first evaluate and try to understand what this for loop is and how much time it will take. In the iteration number one, you can clearly see that i is equal to n by two. right? You can write this as i equal to n by two plus zero.

Now, in the iteration number two, it is clear that, this will be i equal to n divided by two plus one. Because you can clearly see over here that this is i plus plus. An increment by one step. So, obviously in the next iteration, this will be n by two plus one. In the iteration number three, this will be n by two plus two. In the iteration number four, this will be n by two plus three and so on. Now, let us assume that we are running upto iteration number k, in that case i will be equal to n by two plus k minus one.

Here you can clearly see in the iteration number one, this value is zero. Iteration number two, this value is one. While this n by two remains constant, only this value is changing with the iterations, right? In the iteration number three, this will be two. Iteration number four, this is three. So similarly, in the iteration number k as well, this will be k minus one. So I will be n by two plus k minus one, which is equal to n. Because this is the last iteration we are considering. But we don't know how many times this has been executed.

That's why I have taken this as k. So at this particular iteration, i is equals to n by two plus k minus one, which is equal to n. Now, let me rewrite this over here in a proper manner. This is n by two plus k minus one equal to n. Let's solve this. We can write this k minus one equals to n minus n by two without any problem. I can bring this n by two over here. By solving this, this becomes k minus one equal to two n minus n divided by two. Again, we can write this as k equals to n by two plus one. This means that our loop is running n by two times. I can take the least upper bound as n without any problem, Loop executes n by two plus one, which can be thought of as n by two times only. Because plus one, if we won't consider, then it will not cause any problem. We can take the least upper bound as n without any problem.

So this loop is actually running n times. Although it is running n by two times, let me tell you, but we are taking the least upper bound without considering the constants. So least upper bound of n by two is obviously n. So we can say that this loop is running in times. So this is big O of n. Now, let's consider the next loop. Here in this case, you have j equal to one and this is quite interesting. Here it is written j plus n divided by two less than or equal to n.

And here it is just j plus plus. Let's see what is happening over here. In the iteration number one, it is clear that j is equal to one, right? In the iteration number two, J is equal to two. Iteration number three, j is equal to three. Iteration number four, j is four and so on. At iteration number k, j will be equal to k without any problem. Because here in iteration number four, we have j equals to four.

Iteration number three, we have j equals to three. So, it is clear that in iteration number k, j is equal to k which is equal to n by two. Why I am writing this as n by two? j plus n by two less than or equal n can be written as j less than or equal to n minus n by two. I can bring this n by two over here.

This becomes n minus n by two. I can solve this and this brings me n by two. So, j is eventually less than or equal to n by two. I can say that k is equal to n by two without any problem. So it is clear from this fact that this loop is running n by two times. I can take the upper bound as n and can clearly say that loop is running with the time complexity big O of n. So, this is the upper bound I can take, which is n instead of n by two. Always try to remove the constants. Don't take n by two. Instead of n by two, you can take a least upper bound that could be n. Now let's see the other loop. Here in this case, obviously we can clearly understand that k is equal to one. and k is less than or equal to n and k is equal to k into two. We have already calculated the time complexity when these loops are available. Here in the iteration number one, k is equal to one, one can be written as two to the power zero, two can be written as two to the power one.

Similarly, eight can be written as two to the power three and so on. If I consider this up to iteration number p, then this will be two to the power p minus one, which is eventually equal to n. Because in the last iteration, two to the power p minus one is n. You can clearly see over here. I can say that two to the power p minus one is equal to n or n is equal to two the power p minus one without any problem. I can take log on both sides. This will become p minus one equal to log n base two. I can write this as p equal to log n base two plus one, which is equal to big O of log n. I can eliminate this constant. So, I can say that the time complexity for this loop is big O of log n.

Now let me tell you, these are nested for loops, right? So obviously, you know that we need to multiply these three time complexities. n into n into log n, which is equal to big O of n square log n. So, I can say that the time complexity for this particular code is big O of n square log n or order of n square log n. So, this is the time complexity of this particular code.

This loop is running n times. I have taken the upper bound. This loop is also running n times. Again, I have taken the upper bound. Here in this case, this loop runs log n times. This is nested for loop structure. So here, in this case we need to multiply these three time complexities. n into n into log n will give us n square log n, which is the final time complexity. This statement is executing n square log n times. So, this is the time complexity of this particular code. Now, here is one homework problem for you. The program is available in front of you. Again, we have three nested for loops. You need to determine the time complexity of this program. And obviously, you can post your answers in the comment section below. Okay friends, this is it for now. Thank you for watching this presentation.
.