Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Suppose that I have a turing machine that receives as input the string $1^{n\times n}$ (unary input), what is the time complexity of writing $p_1,...,p_n$ on the output tape, where $p_i$ is the i-th prime number (written in binary)? And writing the first $n$ primes followed by their product (all written in binary)?

share|improve this question
    
Homework? What did you try? –  Pål GD Jan 30 '13 at 20:43
    
What does $1^{n \times n}$ mean; $n^2$ many ones? –  Raphael Jan 30 '13 at 20:59
    
Yes. I only know that in order to find n primes I must check at least n*log(n) numbers. So for every x in 2..n I can mark every non prime number x^i using the Sieve of Eratosthenes up to n^2 O(n^2*log(n)*log(log(n))). Whenever I find one I can write it on the output tape O(log(n)) –  user6638 Jan 30 '13 at 21:29

1 Answer 1

up vote 2 down vote accepted

Since the input is of length $n^2$, it makes sense that the TM must read it at least once (to learn the value of $n$), and we have a trivial lower bound of $\Omega(n^2)$. It is my understanding that what you actually ask is "can we complete the task with $O(n^2)$ steps as well"?

You suggest using the Sieve of Eratosthenes to mark primes. This is a clever idea. Indeed, a possible TM can run over the input. Each time it finds a 1, it writes its index on the output tape ($p_i$), and go through the input tape, zeroing any multiply of $p_i$. Then it goes back to index $p_i$ and repeat.

In order to know the index, we can assume the TM maintains a counter on the output tape (which is being "pushed" every time the TM outputs a new prime).

Now let's analyze the running time.

  1. reading the input - $n^2$
  2. For any prime we find (and we have $n$ of those:)
    1. mark the input tape according to the Sieve of Eratosthenes: we need to go through approximately $O(n\log n)$ numbers due to the density of primes - $O(n\log n)$
    2. push the index and write the output - $O(\log n)$
    3. counting exactly $p^i$ steps between two indexes we zero - $O(n\log^2n)$
  3. Multiplying all primes - $O(n^2\log^{1+\epsilon}n)$

so the naïve solution above takes $O(n^2) + n\times [ O(n\log n) + O(n\log^2 n)] + O(n^2\log^{1+\epsilon} n)= O(n^2\log^2n)$. In the above I assumed counting takes $O(n\log^2 n)$ since each step we need to subtract 1 from a $\log n$-long number, for every step in the sieve (which we bound to length $O(n\log n)$).

The time complexity of that algorithms is $O(n^2\log^2 n)$.

However, things can get better, as there are other ways of sieving. Assuming a multitape TM, the sieve of up to $k$ can be computed using $O(k/\log\log k)$ additions (thus, with $O(k\log k/\log\log k)$ bit-operations) by [1]. By setting $k=O(n\log n)$, we can compute the sieve with $O(n\log n)$ steps.

However, computing the multiplication of $n$ numbers (of length $\log n$) will take $n \times O(MUL_{\log n})$ where $MUL_k$ is the time to multiply two numbers of length $k$. According wikipedia, $MUL_k \approx O(n\log n )$ [2]. This step alone is $\Omega(n^2\log n)$ and I don't see much hope to get complexity of $O(n^2)$.


[1]: A. O. L. Atkin and D. J. Bernstein, "Prime sieves using binary quadratic forms" (free-access), Mathematics of Computation 73 (2004), pp. 1023–1030.
[2]: ignoring the practically constant term of $2^{\log^* n}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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