- #1

zak100

- 462

- 11

- TL;DR Summary
- From the internet, I found that the running time of algorithm to find prime number is O(sqrt(N)).

I have 3 questions: Can we say that the running time is O(log^2N) for detection of Prime number? For large values of N, can we say that its a pseudo-polynomial algorithm? Is this true for Sorting algorithms also?

Zulfi.

Hi,

I want to know if the algorithm to find prime number has running time O(sqrt(N)) or O(log^2N). log^2N is better than sqrt(N). Also for large values can it become a pseudo polynomial algorithm?

Zulfi.

I want to know if the algorithm to find prime number has running time O(sqrt(N)) or O(log^2N). log^2N is better than sqrt(N). Also for large values can it become a pseudo polynomial algorithm?

Zulfi.