Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given these two computational complexities of 2 algorithms:

$\exp(O(\sqrt{\log n \log \log n}))$

$O(\sqrt{\exp n} / \log{ \sqrt{ \exp n} })$

where I imagine the first one goes to infinity slower than the second one, what could be a "simple" function $F(n)$ such that, when multiplied by the second complexity, makes it go to infinity with "same speed" of the first one ? (Lets say, more precisely, so that the ratio of the functions be asymptotically bounded)

[Note that the first expression comes essentially from Wikipedia:, while the second would like to represent a simple process of division by the primes present before the square root of the number being factored]

share|cite|improve this question
As I recall $O()$ and $\exp$ do not commute-is what you want for the first $O(\exp(\sqrt {\log n \log \log n}))$? Note that $\log \sqrt{\exp n}=\frac n2$ (maybe with a multiplicative constant depending on your base of logarithms). So the second is $O\left(\frac 2n \sqrt {\exp n}\right)$ – Ross Millikan Dec 17 '12 at 3:32
Actually the first expression was taken by wikipedia (complexity of best algorithms). See: – Pam Dec 17 '12 at 7:56
My goal was to understand how much the best algorithms outperform an (imaginary) simple process of trial over the primes preceding $\sqrt(n)$, which are $\sqrt(n)/\log(\sqrt(n))$, assuming equal to $0$ the cost of producing and accessing the list of primes. (My expression has exp(n) because in the first one, n is the number of digits, and not the number being factored.) – Pam Dec 17 '12 at 8:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.