3 ms·
In my opinion space limited solutions are not very interesting. Time complexity is always >= space complexity, so finding optimal time solutions is always more
by andrewp123 3y ago
In my opinion space limited solutions are not very interesting. Time complexity is always >= space complexity, so finding optimal time solutions is always more interesting. And we already knew the optimal time complexity. I appreciate a theoretical time vs space relation, but it doesn’t seem applicable to other areas.
- dkural 3y agoFor achieving speed, often you'd like to keep your hash table in RAM. Space limits result in speed trade-offs. This is very much a real-world concern when writing genome aligners. Hash-based mappers were at a disadvantage early on due to the memory constraints of most servers back around 2009-2012, thus the more efficient Burrows-Wheeler transform based algorithms became popular, partly due to significantly reduced RAM needs - one could now align genomes on a laptop!
- tdstein 3y agoIt’s a great thing that this report addresses both space and time!