input: n-bit integer X

output: list of prime factors and their multiplicity

acc = X

for i = 2 ... sqrt( X )

--count = 0

--while acc % i == 0

------acc = acc / i

------count = count + 1

--if count > 0

------print i (count)

I know that for the worst case, a n-bit integer is 2^n maximum.

So the time complexity for for i = 2 ... sqrt( X ) is 2^(n/2)-1

Now I'm really confused with the time complexity of while acc % i == 0

For the worst case, let's say that the n-bit number X is a prime. Then the while loop will not be executed at all. How can I define its time-complexity?

How can I find the Big-O of this algorithm? Is iit O(2^n) or O(2^(n/2))


1 Answer 1


Your algorithm takes $O(X^{1/2})$ in the worst case, which isn't too bad, but it also takes $\Theta(X^{1/2})$ in the best case. That's because you always test divisibility by all numbers up to $X^{1/2}$ even when it is clear that you found all factors of X already.

The loop testing acc % i = 0 is negligible, because X has at most $\log X$ factors.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.