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?
start,endwouldn'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. $\endgroup$