1
$\begingroup$

I want to find the all primes between 2 and $k-1$. We can come up with an $O(k\log k)$ running time algorithm. I want to compute this set in $O(k)$ running time. For this algorithm is :

enter image description here

we are maintaing a one pointer from node $i$ of the list $L$ to index $i$ of array $N$ and one pointer from index $i$ of $N$ to $i$th node of list $L$. We will use a doubly linked list in such a way that we mark each element of $N$ exacly once.

  1. Pick the smallest unmarked element $i \ge 2$ in $N$ and add $i$ to $Q_{k-1}$.
  2. Starting from the first node, walk up the list $L$ in increasing order until we find the smallest number $r$ in it such that $r\cdot i \ge k-1$.
  3. Walk down the list $L$ (crucially, in decreasing order) from the node $r$, and for each $l$ in $L$, seen, mark the element $N[i\cdot l]$ and delete the node containing $i\cdot l$ from $L$ ( this node in $L$ is accessed through the pointer from the $(i\cdot l)$th location in $N$ ).
  4. If $N$ has any unmarked element $\ge 2$, go back to first step

In the first round all the multiple of 2 will get marked. It is easy to verify that each element in the array will get marked just once.

Question : How to show that above algorithm has Running time $O(k)$?

After first iteration all multiples of 2 will be marked in the array $N$ and all multiples of 2 will be removed from the list $L$. In the second iteration multiples of 3 and so on.

$$ \begin{align*} \text{Total time}: &= c_1k + c_2\frac{k}{2} +c_3\frac{k}{2 \times 3} +c_4\frac{k}{2 \times 3 \times 5} + c_5 \frac{k}{2 \times 3 \times 5 \times 7}+\cdots\\ &=k \left(c_1 + c_2\frac{1}{2} +c_3\frac{1}{2 \times 3} +c_4\frac{1}{2 \times 3 \times 5} + c_5 \frac{1}{2 \times 3 \times 5 \times 7}+\cdots \right) \\ &= O(k) \end{align*} $$

Reference : link

$\endgroup$
  • $\begingroup$ This is the Eratosthenes sieve, whose running time is $O(n\log\log n)$. $\endgroup$ – Yuval Filmus Feb 11 '18 at 18:55
  • $\begingroup$ The answer to a prior question of yours already described how to compute this set in $O(k)$ running time, and gave you references that analyze the running time of various algorithms of this sort (including the algorithm you describe, I believe): cs.stackexchange.com/q/87602/755 $\endgroup$ – D.W. Feb 12 '18 at 0:27
  • $\begingroup$ @Yuval Filmus No the running this is a special case of " sieve of Atkin " whose run-time is $O(k)$. you can check the link given above and in the reference part (second reference 2 ,page 990, second last paragraph) $\endgroup$ – Complexity Feb 12 '18 at 5:44
  • $\begingroup$ @D.W. Algorithm is clear to me to some extent. This question if for runtime analysis. $\endgroup$ – Complexity Feb 12 '18 at 5:47
  • $\begingroup$ How do you get the total time formula? Could you please explain more? $\endgroup$ – xskxzr Feb 12 '18 at 9:55
0
$\begingroup$

The key is already shown in your link: each composite number is marked only once in this algorithm.

Consider a composite number $x=p_1^{\alpha_1} p_2^{\alpha_2}\cdots$ where $p_1<p_2<\cdots$ are primes and $\alpha_1,\alpha_2,\ldots$ are positive integers. In the iteration for $p_i$ ($i>1$), note $p_1^{\alpha_1} p_2^{\alpha_2}\cdots p_i^{\alpha_i-1}\cdots$ has been deleted from $L$ in the iteration for $p_1$ because $p_1^{\alpha_1} p_2^{\alpha_2}\cdots p_i^{\alpha_i-1}\cdots$ is a multiple of $p_1$, so $x$ will not be marked in the iteration for $p_i$. As a result, $x$ will be marked only once in the iteration for $p_1$.

In each iteration, traveling the list costs the same asymptotically as the marking process, because each element in the list corresponds to a number to be marked.

Hence the total time is equal to the time for marking asymptotically, which is $O(n)$.

$\endgroup$

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.