Consider the following algorithm that gets an integer m an n

Consider the following algorithm that gets an integer m (an n-bit integer) as input and determines whether m is a prime or not. Input: m x = squareroot (m); for(int i = 2; i

Solution

The best case time complexity of this algorith is O(1) as when the number is divided by 2 it can be terminated in the 1st check. eg 16

The worst case time complexity of this algo will be O(sqrt(n)) as when the number is prime it will run till the end in while loop and at the end loop will be terminated

eg 13