Discussion Overview
The discussion revolves around the running time of algorithms for detecting prime numbers, exploring different complexities associated with various algorithms, including O(sqrt(N)) and O(log^2N). Participants also touch upon the implications of input size on algorithm performance, particularly in relation to polynomial and pseudo-polynomial classifications.
Discussion Character
- Debate/contested
- Technical explanation
- Mathematical reasoning
Main Points Raised
- Some participants propose that the running time for finding prime numbers is O(sqrt(N)), while others suggest that O(log^2N) may be better.
- One participant notes that primality testing is polynomial with respect to input size and is not NP-complete or NP-hard.
- Another participant mentions that the average case running time for primality testing can be O(sqrt(N))/log N.
- There is a question raised about why algorithms like knapsack can change from polynomial to pseudo-polynomial with large input sizes, while prime number detection does not exhibit the same behavior.
- The time complexity of the sieve of Eratosthenes is mentioned as O(n log log n), suggesting a different approach to prime detection.
Areas of Agreement / Disagreement
Participants do not reach a consensus on the running time complexities of prime number detection algorithms, with multiple competing views presented regarding the classifications and implications of different algorithms.
Contextual Notes
Participants express uncertainty regarding the specific algorithms being referenced and the conditions under which different complexities apply. There are also unresolved questions about the relationship between input size and algorithm performance.