user923005 wrote On 03/06/07 13:12,:

> On Mar 6, 2:30 am, "Subra" <(E-Mail Removed)> wrote:

>

>>Hi,

>>

>> What is the best way to find the 1000 largest numbers from the file

>>having hell lot of entries ? Can you please help me to find out the

>>way ? Do I need to go for B+ trees ??

>>

>>Please help,

>>Subramanya M

>

>

> Your question is better suited to news:comp.programming.

>

> The answer to your question is called Quickselect() and is described

> in detail in:

> T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to

> Algorithms, Cambridge: The MIT Press, 1990.
Observation #1: The "Quick Select" Google turns up

chooses *one* value from a set, not a thousand.

Observation #2: It also needs random access to the

entire set, which consists in this case of a billion

elements.

> It's O(N). All the other solutions posed here are O(N*log(N))
Observation #3: This is wrong. For (counter-)example,

I suggested using a heap, whose time complexity would be

O(N*log(1000))=O(N).

--

(E-Mail Removed)