Let NextPrimeNumber be an oracle that accepts a prime number n and returns the smallest prime number m such that m > n. It can be called by a Turing machine and returns the answer in constant time.

Let F be the Turing Machine that receives K a positive integer as a number. Suppose its code is the following:

current_prime = 2
while (current_prime <= K):
  current_prime = NextPrimeNumber(current_prime)

What is the time complexity of F?

If we printed out all numbers from 2 to K then it would take exponential time in terms of the bit length k of K. However we only iterate only over the primes, not all numbers from 2 to K. I believe primes represent 1/ln(K) of primes less than or equal to K. Therefore the time complexity would be: (2^k)/ln(K) - which would still be exponential or at least super-polynomial?


1 Answer 1


The running time is $O(K/\ln K)$. This is an exponential running time: the input takes $\lg K$ bits (assuming $K$ is specified in binary), so the running time is exponential in the length of the input. If you set $k=\lg K$, then the running time is $O(2^k/k)$, which is an exponential function of $k$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.