Time and Space Complexity of Prime factorization 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 &lt;= 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 &lt; 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 &lt;= 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 &lt;= Math.sqrt(number); i++) {
      if (number % i == 0) {
        return false;
      }
    }
    return true;
  }


static int getNextPrimeNumber(int number) {
    while (!isPrime(++number)) {
    }
    return number;
  }
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 &lt; 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 &lt; 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 &lt; divisor * divisor

if stopped, and number > 1:


number is last factor