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
    @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
    @tomasz -- you're right. I fixed my answer. Thanks.2012-11-19