Runtime of prime factorization algorithm

Question

Consider an algorithm that takes in an integer N and divides out all the factors of 2, then 3, then 4, all the way up to about sqrt(N). If it takes unit time to add, subtract, multiply, and divide integers, how fast is this algorithm? What about if it takes Theta(n) time to add, subtract, multiply, and divide two n-digit binary numbers?

My thoughts:

In order to better understand the problem, I first wrote some pseudocode outlining the algorithm. I think it looks something like this.

factorize(N) { for (i = 2; i <= sqrt(N); i++) { let r be the remainder obtained by dividing N by i. while (r == 0) { N = N / i; print i # Print the prime factors of N. } } }

I'm pretty sure the algorithm is O(sqrt(N)) just from trial-and-error (plugging in values). I think this worst-case is exhibited when N is prime. However, I'm not completely sure about this.

Now I'm also confused about how this runtime changes if it takes Theta(n) time to add, subtract, multiply, and divide two binary digits. This seems a lot harder to analyze for some reason since we're performing a division on every iteration. If I had to guess, I would say O(N^(3/2)), which is just my old answer multiplied by N, but I'm even less sure about this answer.

Could someone please help me?

Prune · Accepted Answer · 2020-02-05 18:02:14Z

You're quite correct on the first algorithm: worst-case is when N is prime, and you have no factors. Your loop runs for sqrt(N)-1 iterations, O(sqrt(N))

For the second algorithm, the missing insight is that the quantity of digits in N is ceil(log(N, base=2)). For computing complexity, simply use n = log(N).

From what you've already covered, I expect that you can finish from here: your division operation is now O(log N) rather than O(1).

Collectives™ on Stack Overflow

Runtime of prime factorization algorithm

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related