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

2

After the first step, what remains is $N/2$ items.

After the second step, what remains is $2/3$ of these, i.e. $(2/3)*(N/2)$ items, or $N/3$

After the third step, what remains is $3/4$ of these, i.e. $(3/4)*(2/3)*(N/2)$ items, or $N/4$.

The pattern should be obvious, now: after $n$ removal steps, what remains is $N/(n+1)$ items.

So, if you want the remainder to be 0 or 1 items, then you have to choose $n$ so that $N/(n+1) \le 1.$

  • 0
    Thank you. But that would mean it takes more than N steps. Would it not? Which seems very strange, as i am removing *much* more than 1 element at a time (a fraction of the remaining elements). Am i getting this wrong ? I was actually expecting, for the number of steps, something more similar to some power of log(N), which is what we get by using a constant fraction, like 1/2.2012-11-18
  • 0
    I think it should actually be $N/(n+1)\leq 1$. So yeah, looks like I was wrong about the bounded $S$, this looks pretty linear to me. ;)2012-11-18
  • 0
    @sara: Why is it so surprising? $\sum_{j=2}^\infty 1/2$ grows to infinity *much* faster than $\sum_{j=2}^{\infty} 1/j$. ;) (I'm not saying those are directly related, it's just an example.)2012-11-18
  • 0
    Ok. Thanks a lot!2012-11-18
  • 0
    @tomasz -- you're right. I fixed my answer. Thanks.2012-11-19