Thread: Help with question on computation time?

Can someone help with this question?

Rank the following in order of computation time from quickest to slowest, with m and n being 100 diget random numbers.

1. factor m
2. find gcd(m,n)
3. find two "probable primes" larger than m with a probabilty error of less than 10^-8

The answer lists them as 2,3,1

why is this? i would of thought 3 would be slowest and 1 quickest

Originally Posted by BruceBronson

Can someone help with this question?

Rank the following in order of computation time from quickest to slowest, with m and n being 100 diget random numbers.

1. factor m
2. find gcd(m,n)
3. find two "probable primes" larger than m with a probabilty error of less than 10^-8

The answer lists them as 2,3,1

why is this? i would of thought 3 would be slowest and 1 quickest

Look at your notes for the algorithms to do these things and compare
operations counts.

You could also look at the computational complexity of the problems, but that
would not answer the question as it refers to a particular size of problem
(though I expect that is what your instructor expects you to do).

RonL