suppose x_i is the number of new elements covered in the i-th iteration.
let us use S_i to denote the total number of elements covered after the i-th iteration. In particular, we have S_i = x_1+x_2 +...x_i.

Let us use r_i to denote opt -S_i.

We know that x_i > r_i /k. Therefore, r_i = r_(i-1)-x_i <= r_(i-1) *(1-1/k)<= opt(1-1/k)^i.

After the k-th iteration, we know that r_k <= (1-1/k)^k * opt<= 1/e*opt

Therefore, we know that Alg = S_k = opt -r_k >=  opt(1-1/e)