Algorithm for Prime Number

[zak100]

Hi,

This is not a HW.

Algorithm for prime number x 2<=I <= x -1, test whether x is divisable by i,

 

Can we say that the running time is O(log^2 x) time, for large values of x can we say that the algorithm is a psedudo-polynimial time algorithm.

 

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.

[Ghideon]

On 3/9/2020 at 5:46 AM, zak100 said:

Algorithm for prime number x 2<=I <= x -1, test whether x is divisable by i,

Ok. That algorithm is not something I would consider using in a real case.

On 3/9/2020 at 5:46 AM, zak100 said:

Can we say that the running time is O(log^2 x) time, for large values of x can we say that the algorithm is a psedudo-polynimial time algorithm.

Why do you think that the algorithm you posted has logarithmic complexity? 

On 3/9/2020 at 5:46 AM, zak100 said:

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

A simple prime number algorithm can run in O(sqrt(N)). But not the algorithm you posted. Maybe you could post the algorithm you wish to discuss?

 

On 3/9/2020 at 5:46 AM, zak100 said:

This is not a HW.

It's posted in homework section, hence I answer according to the rules in this section.

 

Edited March 10, 2020 by Ghideon
clarification

[zak100]

Hi,

Thanks for your reply.

Please reply me about pseudopolynomial behavior for large values of 'n' for sorting algorithms like Bubble sort?

 

Zulfi.

Edited March 11, 2020 by zak100

[Ghideon]

7 hours ago, zak100 said:

Please reply me about pseudopolynomial behavior for large values of 'n' for sorting algorithms like Bubble sort?

I think more details are needed to make a comment. Otherwise I would have to write a rather long article to cover the topic. For instance, when you say "n" and sorting do you mean that there are n items to sort? Or do you imply that the algorithm is given some number of integers where all integers are less or equal to n? When stating "sorting algorithms like Bubble sort" do you mean a set of impractical algorithms that like bubble sort runs in O(n^2)?