LFSR Output Sampling for Berlekamp-Massey
Berlekamp-Massey is designed for the situation where you have observed $2n$ consecutive output bits from a $n$-bit LFSR.  It doesn't work if the observed bits are scattered randomly, at random non-contiguous offsets in the stream.

Information-theoretically, a minimum of $2n$ bits of output are needed to reconstruct the LFSR.  Intuitively, this is because there are $2n$ bits of unknowns: the unknown $n$-bit state of the LFSR, and the unknown $n$ bits on the taps (the feedback polynomial).  Therefore, Berlekamp-Massey exactly meets the known lower bounds, in the case where you get to observe consecutive output bits.

Of course, you could also have used linear algebra to solve for these $2n$ unknowns, but Berlekamp-Massey is faster than solving a system of linear equations ($O(n^2)$ instead of $O(n^3)$, or something like that).

The number of observations you need depends only on the size of the LFSR, not on the output bits.  If you do know the size of the LFSR, you don't need to see any output bits to predict how much output will be needed.  If you don't know the size of the LFSR, seeing a few output bits doesn't help you predict the size of the LFSR and doesn't help you  predict how much output will be needed.

One cool thing about Berlekamp-Massey, though, is that you don't need to know in advance what the size of the LFSR is (what $n$ is).  You can just start running Berlekamp-Massey on the output stream, and it will generate candidates for the LFSR initial-state and feedback polynomial.  After each bit of output, it will update its candidate.  Once you've observed $2n$ bits of output, you are guaranteed that its candidate is correct.  If you don't know what $n$ is, you can take each candidate and test it against the next few output bits; this will let you recognize when Berlekamp-Massey has finally found the right candidate, i.e., when you've observed enough output stream (it'll let you recognize when you've hit the $2n$ limit, even though you don't know $n$ a priori).