Re: [algogeeks] Re: Cliched 'k' largest elements in billion numbers: Heaps or median-of-medians?

2011-12-13 Thread atul anand
@Gene : considering m-of-m algo , one thing that worries me is that using m-of-m for huge data is not good bcoz when practically implementing it constant would be very large so as to make it work for O(N) here is the reason why is not a good approach for huge data :- reccurence eqn for m-of-m is

[algogeeks] Re: Cliched 'k' largest elements in billion numbers: Heaps or median-of-medians?

2011-12-12 Thread Gene
If N is big enough so that all data will not fit in main memory and k is small enough so that the k top elements fit in memory, then the heap is likely to be the best.This is because disk access is so incredibly slow compared to memory access: A few milliseconds (10^-3) vs. a few nanoseconds