# Relationship between an integer N and the number of bits n required to represent the integer

I'm trying to understand the time complexity of the following code in terms of n.

Pseudocode for trial division: I understand that the time complexity of the algorithm is O(sqrt(N)). However, can someone explain how the person in the link below came up with O(e^(n/2)). In other words, what's the mathematical relationship between N and n? Thanks.

Time complexity explanation: • Welcome to CS.SE! We ask that questions here be self-contained, so they can be understood without following any external links. I've edited your post to put the images inline (I know you can't include more than one image, as a new user). However, please don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. (continued) – D.W. Oct 21 '16 at 19:50
• Please transcribe text and mathematics -- note that you can use LaTeX -- and don't forget to give proper attribution to your sources! – D.W. Oct 21 '16 at 19:50
• Is this pdf the source of the images? – Evil Oct 21 '16 at 20:17

The integer $N$ takes $\log_2 N$ bits to write down. Set $n = \log_2 N$. Then $N = 2^n$, so $\sqrt{N} = 2^{n/2}$.
I'd guess they are using the natural logarithm (to base $e$), which is where they get $e$ instead of $2$. That's a bit odd but I suppose it is valid.