Let's discuss problem number 2 on time complexity of loops. The topic is time complexity of loops solved problem. Let's proceed and let's see the problem first. Here is the problem. Consider the following C code segment.
This is the C code segment. Let Tn denote the number of times the for loop is executed by the program on input n. So, Tn represents the number of times or the frequency count of the for loop, this for loop which is executed by the program on input n. Which of the following is true? These are the options and our job is to determine the correct option.
Here, in these options, we can observe Tn is represented in terms of big O and big omega notation. So, we will also represent Tn in terms of big O and big omega notation. We know Tn represents the frequency count of this for loop.
So, now let's try to solve this problem. For this, let's remove these statements and the options and let's focus on this code. This is the code from the question.
And now we are ready to solve this problem. We need to find Tn which represents the frequency count of the for loop. How do we find Tn? We know Tn represents the frequency count of this for loop or the number of times this for loop will execute.
In order to find Tn, let's first understand the working of this for loop. In this for loop, we are initializing i to 2. Then we are comparing i with square root of n. This function sqrt has the capability to calculate square root of a number. The number we are providing to it is n. So, it will calculate the square root of n.
We are comparing i with square root of n. After this, what happens? If this condition is satisfied, then this block of code will execute and i is incremented by 1. This is how a for loop works. First, the condition is checked.
The block of code within it will execute if the condition is satisfied and then the increment happens. Then again, the condition is checked. The block of code executes if the condition is satisfied and increment happens.
If the condition is not satisfied, then the loop will terminate. So, in this way, the for loop executes. Now, within this for loop, we have this if construct. Here we are checking if n mod i is equal to 0. Then execute these two statements. In other words, we are asking is it true that n is not a prime number?
Here we are checking n mod i equal to 0. We are comparing n mod i with 0. If n is divisible by some number, or if the remainder of n mod i is 0, then not prime should be displayed on the screen and 0 must be returned from this function. Because of this statement, the loop will terminate in between or in other words, it will terminate abruptly. This means this loop will not complete its iterations. It will not execute up to square root of n.
It will terminate abruptly. This happens because of this statement. So, one thing is clear.
If the number is not prime, then the loop will terminate abruptly, that is in between. But if the number is prime, that is if n is prime, then the loop will not terminate abruptly because this condition will never satisfy. This loop will terminate normally. This means this loop will complete all its iterations.
And therefore, this statement will execute. This means value 1 will be returned from this function and which indicates that the number n is prime. So, I hope the code is clear. Now, we know how this for loop works.
Let's try to find the value of tn. We need to find tn in terms of asymptotic notation. As mentioned in the options, we need to represent tn in terms of big O. and big omega.
In order to find Tn and to simplify the discussion, Let's take the for loop with a simple statement in place of this if construct. So, now we need to replace this if construct by a simple statement. This allows us to understand the importance of this if construct. So, now let's consider the following loop. In this for loop, i is initialized to 2. i is compared with square root of n.
and i is incremented by 1. Within this for loop, we have a single statement and this statement is not a construct like if, it's a simple statement. We don't know what this statement is, but I am assuming it is some statement or an expression. Here I have replaced sqrt by square root symbol.
This is done for the sake of simplification and understanding. Now, What do you think what is the time complexity or the frequency count of this for loop? We need to determine the tn of this for loop. Let's now try to find tn for this for loop. This is the for loop.
In order to find tn for this for loop or the frequency count of this for loop, we need to analyze each iteration of this for loop and we need to observe the values of I carefully. In the iteration number 1, the value of I is 2. So, let's write I equal to 2 here. After this, I is compared with square root of n. Let's say 2 is less than square root of n. The condition is satisfied.
Therefore, the statement within this for loop will execute. I am assuming this is a simple statement. It will execute and after this, I is incremented by 1. So, in the second iteration, the value of i is 3. 2 plus 1 is 3. That's why the value of i in the second iteration is 3. Now, 3 is compared with square root of n. Let's say the condition is once again satisfied. The statement will execute and i is incremented by 1. So, this time we will get 4 as the result of i.
So, in the third iteration, the value of i is 4. Similarly, in the fourth iteration, the value of i is 5 and this will continue up to let's say k. I am assuming k is the last value of i for which this condition is true. So, I am assuming k is equal to square root of n. So, k is equal to square root of n and this means this loop will run square root of n minus 1 times.
Why? We can replace k by square root of n. This is the last value of i for which this condition is true.
And we can observe that i is initialized to 2, not 1. So, starting from 2, the value of i goes up to k, that is square root of n. So, there are a total of square root of n minus 1 iterations. Therefore, this statement will execute square root of n minus 1 times.
And this means the frequency count of this for loop is square root of n minus 1. But now we need to represent the frequency count in terms of asymptotic notation. We can represent square root of n minus 1 as theta of square root of n. Here I have removed minus 1 and the dominating term is square root of n.
Therefore, within the theta notation, I have mentioned square root of n. Why I have written theta notation here? The reason is simple.
The best case and the worst case time complexity of this for loop is same. It is square root of n. This means the upper bound of this for loop is square root of n and the lower bound is also square root of n. Instead of writing theta of square root of n, we can also write big O of square root of n and big omega of square root of n.
In place of big O and big omega, I have mentioned theta, which means the same. So, the time complexity or the frequency count in terms of asymptotic notation is theta of square root of n. Here, we can observe we have a simple statement.
This is not an if construct. But in the actual question, we do not have a simple statement. we have an if construct like this. Due to this if construct, the best case And the worst case of this for loop is not same. Why?
Because as mentioned earlier, it might be possible that this condition is satisfied for some value of i. In that case, the loop will not run square root of n minus 1 times. It will run less than square root of n minus 1 times.
So, one thing is clear that Best case and worst case due to this if construct are not same. Now, we need to determine the best case and the worst case of this for loop and accordingly, we need to write the time complexities. Let's do this now. Let's do the best case analysis first.
Now, let's write this for loop here for analysis. Here we have a small change. In place of sqrt function, in the condition, we have this square root symbol. Now, let's try to find the best case of this for loop.
We know the best case occurs when this condition is satisfied. When this condition is satisfied, return 0 statement will execute and the loop will terminate abruptly. This means in between.
This means this loop will not run for values of i from 2 to square root of n. It will run less than square root of n times. Now, let's assume some value of n.
We know this condition is satisfied when n is not a prime number. So, let's assume some n which is not a prime number. Let's assume n is equal to 16. We know 16 is not a prime number.
Now, let's replace n by 16. We will get square root of 16 here. What is square root of 16? Square root of 16 is 4. So, now we have 4 here in this condition. We know i is initialized to 2. So, in the first iteration, the value of i is 2. Now, 2 is compared with 4. Is 2 less than or equal to 4?
We know 2 is less than 4. Therefore, this condition is satisfied. Hence, This block of code will execute. Now, within this if construct, we are checking this condition.
Is n mod i equal to 0? Let's replace n by 16. So, we will get 16 here. And let's replace i by 2 because in the first iteration, the value of i is 2. Now, we have 16 mod 2 equal to 0. Can we say, 16 mod 2 is equal to 0?
What is 16 mod 2? We know mod operator gives the remainder of the division of 16 and 2. Is the remainder of 16 divided by 2 equal to 0? Yes, 16 mod 2 is equal to 0. Therefore, this condition is satisfied.
Hence, this printf function will execute and this return statement will also execute. This means in the first iteration itself, the loop will terminate. So, there is only one iteration of this for loop for this value of n.
If we have a simple statement here in place of this if construct, then this for loop will execute 3 times for values of i from 2 to 4. So, there are a total of 3 iterations if there is a simple statement here in place of this if construct. But because of this if construct, there is only one time execution of this for loop and that too for value of n equal to 16 which is not a prime number. So, we can observe the best case is a constant.
Hence, the time complexity is omega of 1. Why I have mentioned omega here? Because here I am talking about the best case. The best case of this for loop is omega of 1. 1 represents the lower bound of this for loop.
It is a constant because of this if construct. Here we can observe we just have one iteration and 1 is a constant. Therefore, the time complexity is omega of 1. Now, we know what is the best case time complexity of this for loop. Now what about the worst case? The worst case happens when this loop runs normally.
or in other words, when this condition is never satisfied. We know this condition will not satisfy when n is a prime number. We can assume any prime number and for that prime number, this condition will never satisfy and hence this loop will run normally for values of i from 2 to square root of n. This means this loop will run square root of n minus 1 times And hence the time complexity is O of square root of n. So, the worst case time complexity of this for loop is O of square root of n.
Here I have mentioned big O notation because we are talking about the worst case time complexity. So, the worst performance or the upper bound of this for loop is square root of n. Now we have two time complexities.
We have the best case as omega of 1 and we have the worst case as big O of square root of n. So, there are two values of Tn. We assumed Tn as the frequency count of this for loop and big omega of 1 and big O of square root of n are the asymptotic representations of the frequency count of this for loop. So, clearly, Option B is the correct option.
Tn is big O of square root of n and Tn is big omega of 1. So, we are done with this topic, time complexity of loops solved problem and we are done with this presentation. Okay friends, this is it for now. Thank you for watching this presentation. I will see you in the next one.