Question

how would you to increase the complexity explain with the help of primality testing

plz ans this que

Answer 1

Answer:

Think about the worst-case runtime of this function, which happens if the number is indeed prime. In that case, the inner loop will execute as many times as possible. Since each iteration of the loop does a constant amount of work, the total work done will therefore be O(number of loop iterations).

So how many loop iterations will there be? Let's look at the loop bounds:

for(int i = 2; i*i <= n; ++i)

Notice that this loop will keep executing as long as i2 ≤ n. Therefore, the loop will terminate as soon as i ≥ √n + 1. Consequently, the loop will end up running O(√n) times, so the worst-case time complexity of the function is O(√n)