Time Complexity as Number of Iterations

Analyzing prime number detection algorithm

Let’s use a normal looping construct to check whether a number is prime. We can write our algorithm in natural language this way:

for each number where integer i starts from 2 to (n - 1)
   if n % i == 0, then n is not prime
   else n is prime

We can test this algorithm using a small positive integer like 11. In that case, if we iterate from 2 to (11 – 1), we’ll see that between 2 to 10, there are no integers that can divide 11 with no remainder. Therefore, 11 is prime. When the value of $n$ is small, our algorithm doesn’t take much time and may appear negligible. Suppose each iteration takes one millisecond (ms). This fraction of a second stands for 10 to the power of -3; if we divide 1 second by 1,000, we get 1 ms.

Note: One microsecond is 10 to the power of -6, one nanosecond is 10 to the power of -9, and one picosecond is 10 to the power of -12.

Now, let’s assume that each iteration takes 1 microsecond. When the number of iterations is small, it doesn’t take much time. However, with the increase of iteration, this time also increases. Instead of 11, we want to check a value like 1000003. The code will iterate more than one million times. Our algorithm appears to crumble because it’ll take a considerable time to finish the iteration process.

Java code for finding primality

We can transport this natural language algorithm to a Java code.