0
$\begingroup$

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

Pseudocode for trial division:

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:

Time complexity explanation

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – D.W.♦ Oct 21 '16 at 19:50
  • $\begingroup$ Please transcribe text and mathematics -- note that you can use LaTeX -- and don't forget to give proper attribution to your sources! $\endgroup$ – D.W.♦ Oct 21 '16 at 19:50
  • $\begingroup$ Is this pdf the source of the images? $\endgroup$ – Evil Oct 21 '16 at 20:17
1
$\begingroup$

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.

See also Complexity of multiplication and Precise runtime of the algorithm to find number of digits in an integer.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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