# Finding the number of iterations to a recurrence

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}$$

-