Let us suppose we are given an integer $\text{N}$ in binary representation. Let us consider the following algorithm to check if $\text{N}$ is a prime.
- For every $i$ such that $2 \leq i \leq\lceil\sqrt{\text{N}}\rceil$, check if $i$ divides $\text{N}$.
- If any of the $i\text{'s}$ divides $\text{N},$ return that $\text{N}$ is not a prime.
- Else, return that $i$ is a prime.
Based on this information, answer the following.
What is the order of magnitude of the running time in terms of the input size? (Assume hypothetically that division can be done in $\text{O}(1)$ time).
