Time and Space Complexity of Prime factorization

Question

I have written a function that prints all the prime factors for a given number. Here is my code

static void printPrimeFactorization(int number) {
 if (number <= 1 || isPrime(number)) { // If given number is already prime, no more factors for it
 System.out.println(number);
 return;
 }
 // check divisibility of given number starting from 2 to nextPrime(that is less than given number)
 for (int nextPrime = 2; nextPrime < number; nextPrime = getNextPrimeNumber(nextPrime)) {
 while (number % nextPrime == 0) { // check divisibility, until number is not divisible
 System.out.println(nextPrime);
 number = number / nextPrime;
 if (isPrime(number)) { 
 System.out.println(number);
 return;
 }
 }
 }
 }

For brevity I am not writing the isPrime() and getNextPrimeNumber() here

I am learning to calculate time complexity, and space complexity. What is the exact time complexity of my code above starting from for loop having while loop in it

I guess Time complexity is O(log n) - Logarithmic time - as the total number of iterations is <= n/2 Correct me if my understanding is wrong Space complexity is O(1) - constant time - As no extra space used other than simple variable assignments.

UPDATE:

static boolean isPrime(int number) { 
 if (number == 0 || number == 1) {
 return false;
 }
 for (int i = 2; i <= Math.sqrt(number); i++) {
 if (number % i == 0) {
 return false;
 }
 }
 return true;
 }

static int getNextPrimeNumber(int number) {
 while (!isPrime(++number)) {
 }
 return number;
 }

• AJNeufeld: It is impossible to say without knowing the time/space complexity of the functions in the loop (isPrime() and getNextPrimeNumber()), but you haven't provided those. However, looping \$n/2\$ times does not mean \$O(\log n)\$. If n was one million, you would iterate 500,000 times where as an \$O(\log n)\$ algorithm might iterate around 20 times.
• srk: Updated question with isPrime() and getNextPrimeNumber() function
• greybeard: (You would need more math than counting nested loops and exponentiating n, like density of primes. Then again, you leave ample room for avoiding doing the same time and again. (Darn - someone else noticed and edited out the cyclomatic tag...))

Answer 1

isPrime()

Complexity

This function contains a simple loop that iterates up to Math.sqrt(number) times, so assuming Math.sqrt(...) can be computed in \$O(1)\$ time, the function has \$O(\sqrt N)\$ time complexity.

Review

This function is terribly inefficient. Math.sqrt(number) is computed \$\lfloor \sqrt N \rfloor\$ times, yet the value is a constant. This should be moved out of the loop.

The function fails when given a negative number. The square-root is returned as NaN, the for loop executes zero times, and true is returned.

2 is the only even prime number. It can easily be called out as a special case (like you are doing for 0 and 1, allowing the for loop to consider only odd numbers starting at 3, which should cut the function time in half.

---

Main Function - Outer loop

Complexity

Consider this loop:

 for (int nextPrime = 2; nextPrime < number; nextPrime = getNextPrimeNumber(nextPrime)) {
 ...
 }

The getNextPrimeNumber(int number) is a simple function which increments a number by one, and tests whether or not it is prime. These two can be combined into an equivalent simpler loop, which is easier to reason about:

 for (int nextPrime = 2; nextPrime < number; nextPrime++) {
 if (isPrime(nextPrime)) {
 ...
 }
 }

Now, we can see that this loop iterates number - 2 times, so isPrime(nextPrime) is called number - 2 times. This gives us a time complexity of \$O(N^{3/2})\$ without considering the inner loop.

---

Inner Loop

Complexity

The inner statement (the while loop) is executed for each prime number the outer loop finds. From the Prime Number Theorem, we know that the number of primes \$π(N)\$ is approximately \$\frac{N}{\log N}\$.

Since the while loop is dividing the number by a constant factor, p, the prime number from the outer loop, it will execute a maximum of \$log_{p} N\$ times. After each division, isPrime(number) is called. This means \$log N\$ executions of a \$O(\sqrt N)\$ algorithm, so the inner statement is \$O(\log N \sqrt N)\$.

Executed for each prime number, this gives \$O(\frac{N}{\log N} \log N \sqrt N)\$, or \$O(N^{3/2})\$.

Since both portions have \$O(N^{3/2})\$ complexity, the overall complexity is \$O(N^{3/2})\$.

Review

The trial division while(number % nextPrime == 0) loop will exit once all of the factors of nextPrime have been divided out of number. isPrime(number) can't become true while more than one factor of nextPrime exist, and since isPrime() is an "expensive" \$O(\log N)\$ operation, it would be more efficient to remove as many multiples of nextPrime as possible, and only then checking if the resulting number is prime. In short, when the while loop executes one or more iterations, the isPrime() should execute once, but if the while loop executes 0 times, isPrime() shouldn't be executed at all.

---

Overall

You've separated isPrime() out from determining the factors of number, but isPrime() determines whether a number is prime or not by doing trial divisions, and you need to do trial divisions to remove factors from number. One function which does both operations would be more efficient:

• divide out as many factors of 2 as possible
• starting with a divisor of 3, and increasing by 2:
  • if number can be divided by the divisor:
  • repeat as many times as possible:
    • number /= divisor
  • stop, if number < divisor * divisor
• if stopped, and number> 1:
  • number is last factor

Answer 2

We can break down calculating the time complexity as below:

• The method isPrime() is O(n^(1/2)) i.e root(n).

• The method getNExtPrimeNumber() is called for k times where k is the difference between the given prime number and the next prime number.It is calling isPrime() method in every iteration. So it is O(k * root(n)) times.

• The while loop is calling isPrime(n) method in every iteration and will run log base nextPrimeNumber(n) times.For example, if nextPrimeNumber is 2 then it is log base 2(n).So total time complexity of while loop is O(log base nextPrimeNumber(n) * root(n)).

• Now for loop is trying to find out the number of prime numbers between 2 and given number(n). As far as I know there is no math formula present to get that based on given number. So lets assume that iteration to be p. For every iteration of for loop, getNextPrimeNumber() is called and the while loop is called. So total time complexity of your for loop would be : O( p * (k * root(n)) * (log base nextPrimeNumber(n) * root(n)) )

This gives O(p*k*n*log(n)).