# Time complexity of printing prime numbers within a range?

What is the time complexity for the given code that prints prime numbers from start to end? Is it $$O(end*\sqrt{n})$$?

/**
* Print prime numbers between start and end inputs
* Time-Complexity: O(end * sqrt(n))
* Space-Complexity: O(1) only one value as input
* @param start, end
* @return
*/
public void printPrimeSeries(int start, int end) {
for (int i = start; i < end; i++) {
if (findPrimeOrNot(i)) {
System.out.println("The value " + i + " is a prime number");
}
}
}

public boolean findPrimeOrNot(int n) {
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

System.out.println("Enter start number for prime:");
int startInput = scanner.nextInt();

System.out.println("Enter end number for prime:");
int endInput = scanner.nextInt();

PrimeNoSeries primeNoSeries = new PrimeNoSeries();
primeNoSeries.printPrimeSeries(startInput, endInput);
}


Notice: That's not my code. It's by mahesh87.

In your case $$n$$ is end - start. In $$O$$ notation $$n$$ represents the problem size, which is the range between start and end in your case. In $$O$$ notation you are interested in the worst case, therefore we can assume that start is always 0. Now $$n$$ is just an alias for end.

As we have defined $$n$$, it's obvious that printPrimeSeries is just $$O(n)$$ (from 0 to end). The method uses findPrimeOrNot that iterates from 2 to Math.sqrt(n), which is $$O(\sqrt{n})$$. Combining both is $$O(n)O(\sqrt{n})$$, which is just $$O(n\sqrt{n})$$.

Notice that the $$O$$ notation tells you something about the asymptotic behaviour of the algorithm. It doesn't matter too much if there are 2 parameters, at least in this case.

So yes, your assumption is fully correct (ignoring that you've written end instead of $$n$$).

Other users have proposed that the correct answer is $$O((end - start)\sqrt{end})$$. I think this is a valid point of view but it doesn't provide any beneficial information in terms of $$O$$ notation for the given case.

Now my question: What is the formally correct way to describe the time complexity of the given algorithm? Is my reasoning valid or is it just plain wrong?

• I wouldn't trust either answer as a good estimation, since many elements $x$ in the interval start,end wouldn't need the $\sqrt{x}$ divisions. That will be needed only for prime numbers or squares of primes. The prime numbers appear in a proportion that gets closer and closer to $\frac{N}{\log(N)}$. The squares of primes in a proportion asymptotic to $\frac{2\sqrt{N}}{\log(N)}$. Half of the numbers (the even ones) require only one division. One third minus one sixth (multiples of $3$ but not even) require only $2$ divisions. ... One needs to sum all the cases. – plop Jul 14 '20 at 18:44

Both "the time complexity is $$O( end \cdot \sqrt{end} )$$" and "the time complexity is $$O( (start-end) \cdot \sqrt{end} )$$" are correct statements (assuming that arithmetic operations on the involved integers can be performed in constant time).
The second upper bound is tighter in some cases. For example, setting $$start=end-10$$ the first upper remains unchanged while the second one simplifies to $$O(\sqrt{end})$$.
Also notice that "In 𝑂 notation 𝑛 represents the problem size, which is the range between start and end in your case." is false. The size of (any reasonable encoding of) the instance is $$O(\log end)$$.
Your function findPrimeOrNot(n) runs in $$O(n^{1/2})$$ in the worst case. Often the execution time is faster. For example for even numbers n, the function returns after a single divisions. But for primes, where all divisors up to sqrt(n) are tested, the execution time is indeed $$\Theta(n^{1/2})$$. And the chance that a random integer x is prime is about x / log x.