Runtime analysis of prime-set computation

Question

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 :

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

Answer 1

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)$.