Hi Guys,(adsbygoogle = window.adsbygoogle || []).push({});

Is algorithmic complexity determined mostly for primality tests or on-to prime-generating functions?

Say, I have the function, Floor[(n!)/(n+1)], and for every n it produces primes, would I have to use the trig definition of the floor function to determine the complexity of this algorithm. Would it be O(n!)?

Now, on the other hand, say, I have the function, Floor[(n!)/(n+1)], where n is an integer that is to be tested for primality, the complexity of this formula is O(n!), right? I would still have to use the trig definition of the floor function, right? Thus rendering this algorithm inefficient because it would take extremely long for the function to test for primality asymptotically.

Note that these are purely hypothetical cases. The above function is neither an on-to prime generator nor a primality test.

Sorry if this question renders me inexperienced because I am. This is my first experience with number theory and algorithmic complexity.

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Algorithmic Complexity and Big-Oh notation

Loading...

Similar Threads for Algorithmic Complexity notation | Date |
---|---|

A How do I supply arpack drivers with all starting vectors? | Dec 24, 2016 |

Issue with behavior of ray-plane intersection algorithm | Jan 28, 2016 |

Algorithm to find square root of a quadratic residue mod p | Feb 14, 2015 |

Algorithmic complexity of primes | Feb 27, 2006 |

Space Complexity of Number-theoretic Algorithms | Feb 15, 2006 |

**Physics Forums - The Fusion of Science and Community**