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 nn 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.

Get hands-on with 1200+ tech skills courses.