Take the 2-minute tour ×

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


  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?
share|improve this question
Read about harmonic series, 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$? –  Golob Nov 18 '12 at 14:53
Do you round up or down? I might be wrong, but I think $S(N)$ is actually bounded. –  tomasz Nov 18 '12 at 14:54
@Golob: She asks to remove $1/m$ from what remains, not the initial total. –  tomasz Nov 18 '12 at 14:55
@tomasz anyhow, what remains might not be divisible by $m$ –  Golob Nov 18 '12 at 15:00
@tomasz I round up (take the ceiling) the removed part, anyway (for what it may matter). –  Pam Nov 18 '12 at 15:10

1 Answer 1

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

share|improve this answer
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. –  Pam Nov 18 '12 at 14:03
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. ;) –  tomasz Nov 18 '12 at 15:03
@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.) –  tomasz Nov 18 '12 at 15:08
Ok. Thanks a lot! –  Pam Nov 18 '12 at 20:08
@tomasz -- you're right. I fixed my answer. Thanks. –  bubba Nov 19 '12 at 0:07

Your Answer


