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.
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
If we printed out all numbers from
K then it would take exponential time in terms of the bit length
K. However we only iterate only over the primes, not all numbers from
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?