0
$\begingroup$

Assume I have an array of $N$ (say $N$ very large) elements.

I proceed removing $1/2$ of the elements then, from what remains, I remove $1/3$ of the elements, then, from what remains, i remove $1/4$ of the elements,

and so on $1/5$, $1/6$ ...

Question:

  1. In how many steps, say $S(N)$, we arrive to $1$ or $0$ residual elements ?
  2. What is the asymptotic behavior of $S(N)$ ? Would that be essentially a logarithm or does it grow faster?
  • 0
    Read about [harmonic series](http://en.wikipedia.org/wiki/Harmonic_series_%28mathematics%29), that might give you some hints. Also, how many elements do I remove when removing $\frac{1}{m}$ when the number of elements in array is not divisible by $m$?2012-11-18
  • 0
    Do you round up or down? I might be wrong, but I think $S(N)$ is actually bounded.2012-11-18
  • 0
    @Golob: She asks to remove $1/m$ from what remains, not the initial total.2012-11-18
  • 0
    @tomasz anyhow, what remains might not be divisible by $m$2012-11-18
  • 0
    @tomasz I round up (take the ceiling) the removed part, anyway (for what it may matter).2012-11-18

1 Answers 1