Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I have an algorithm where the number of items in my set decrease by $\sigma/(1+\sigma)$ on each iteration until all items are exhausted.
$$ \begin{align*} S_0 &= S \\ S_{k+1} &= S_k - S_k \frac{\sigma}{1+\sigma} \end{align*} $$
Here $\sigma$ is a small value.
How can I find number of iterations? I know it is a geometric series but can't seem to simplify for number of iterations.
Presumably the correct form of the recursive step is $$ S_{k+1} \leq S_k - S_k \frac{\sigma}{1+\sigma} = \frac{S_k}{1+\sigma}. $$ Using induction, we can show that $$ S_t \leq \frac{S}{(1+\sigma)^t}. $$ So the algorithm will end by the time $T$ satisfying $$ \frac{S}{(1+\sigma)^T} < 1.$$ I'll let you solve this yourself.
Let $I$ denote the number of iterations and $s$ the size of your set. Then we have
$$I(s)=I(s-\frac{\sigma}{1+\sigma})+1=I(s-2\frac{\sigma}{1+\sigma})+2=\dots=I(s-k\frac{\sigma}{1+\sigma})+k$$
$s-k\frac{\sigma}{1+\sigma}=0$ when $k=s\frac{1+\sigma}{\sigma}$. Therefore
$$I(s)=s\frac{1+\sigma}{\sigma}$$
