3 ms·
1M (ordered) list of numbers requires 3.5MB of RAM(10^6*log_2(10^8) bits). The theoretical lower bound to store unordered numbers is 0.96MB(log_2(comb(10^8+10^6
by YetAnotherNick 7y ago
1M (ordered) list of numbers requires 3.5MB of RAM(10^6*log_2(10^8) bits). The theoretical lower bound to store unordered numbers is 0.96MB(log_2(comb(10^8+10^6-1, 10^6)) bits)
- dan-robertson 7y agoI think your calculation for ordered lists is just wrong. I think the right answer should be about 3.17MB, not 3.5.
- YetAnotherNick 7y agoSomeone wrote 3.5MB, didn't bother to double check but the formula is correct.