Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.