Complexity of prime factor algorithm

Question

I just studied how to find the prime factors of a number with this algorithm that basically works this way:

void printPrimeFactors(N) {

  while N is even
    print 2 as prime factor
    N = N/2

  // At this point N is odd
  for all the ODDS i from 3 to sqrt(N)
    while N is divisible by i
      print i as prime factor
      N = N / i

  if N hasn't been divided by anything (i.e. it's still N)
    N is prime

  }

everything is clear but I'm not sure how to calculate the complexity in big-O of the program above.

Being the division the most expensive operation (I suppose), I'd say that as a worst-case there could be a maximum of log(N) divisions, but I'm not totally sure of this.

Answer 1

You can proceed as like this. First of all, we are only interested in the behavior of the application when N is really big. In that case, we can simplify a lot: if two parts have different asymptotic performance, we need only take the one that performs worst.

The first while can loop at most m times, where m is the smallest integer so that 2^m >= N. Therefore it will loop, at worst, log₂N times -- this means that it performs as O(log N). Note that the type of log is irrelevant when N is large enough.

The for loop runs O(sqrt N) times. At scale, this is way more massive than log N, so we can drop the log.

Finally, we need to evaluate the while inside the loop. Since this while loop is executed only for divisors, it will have a big O equal to their number. With a little thought we can see that, at worst, the while will loop log₃N times because 3 is the smallest possible divisor.

Thus, the while loop gets executed only O(log N) times, but the outer for gets executed O(sqrt N) times (and often the while loop doesn't run because the current number won't divide).

In conclusion, the part that will take the longest is the for loop and this will make the algorithm go as O(sqrtN).