Concerning the runtime of Fermat's Factorisation alogrithm

Question

As part of an exercise I did I had to write pseudocode for the Fermat-Factorisation algortihm. I came up with the following straightforward code:

     Fermat-Factorisation(N):

     for  x ← ceil(sqrt(N)) to N:
         if y2 ← x*x - N is a square:
            return (a + sqrt(y2) and  (a - sqrt(y2)

I am rather sure that this code is correct, but I am unsure about it's runtime. I would have said that this code takes $\mathcal{O}(n)$ time, but a friend of mine said that it takes only $\mathcal{O}(\sqrt{n})$, which I do not really believe.

Could you tell me wether I am right or wrong ?

Answer 1

In order to do a complexity analysis, it pays off to break the problem in parts and see how many operations each part takes.

The inner part of the loop is comprised of simple operations with integers. For most practical applications, we can consider the integers size bounded and thus the time needed for these operations to be in $\mathcal{O}(1)$.

So the only question that really matters is: how many loops does it take?

The number of loops is $\mathcal{O}(N-\sqrt{N})$. Since complexity only cares about asymptotic behaviour, we can ignore the $\sqrt{N}$ term, since it vanishes when compared to the $N$ term as we approach infinity. So the algorithm takes $\mathcal{O}(N)$ operations.