[Solved]: Finding the number of iterations to a recurrence

Problem Detail: 

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.

Asked By : user1008

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9885

3.2K people like this

 Download Related Notes/Documents