Time complexity of printing prime numbers within a range?

Question

I've written an answer to this question, which asks about the following:

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.

My answer to that is:

---

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?

Answer 1

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)$.

Answer 2

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.

You would have to check what exactly the average number of divisions is. With your algorithm, which can be improved, the number of divisions is at least about (end - start) * sqrt (n) / log n and at most about (end - start) * sqrt (n) divisions.

If you want to print the primes, you'll find that printing has such a large constant factor that the execution time of printing about (end - start) / log n primes is much larger than the time for printing the primes, for any reasonable range of primes.