Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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: http://en.wikipedia.org/wiki/Integer_factorization#General-purpose, 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|improve this question
2  
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: en.wikipedia.org/wiki/Integer_factorization#General-purpose –  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

 
discard

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

Browse other questions tagged or ask your own question.