Is the complexity of this algorithm O($\sqrt{n}$) or linear?
No, it would not make the algorithm linear. The worst-case scenario would be $n = m^2 + 1$, where $m$ is some positive integer. In this case, you have an additional $(m+1)^2 - m^2 = 2m + 1$ many tries (since the next square after $m^2$ is $(m+1)^2$ and $n &lt; (m+1)^2$), which is roughly equal to $2\sqrt{n} \in \Theta(\sqrt{n})$.