The Space Race: Progress in Algorithm Space Complexity
This paper presents the first broad survey of the space complexities of algorithms for important problems in computer science, analyzing more than 800 algorithms for different problem families, and comparing the different algorithms for each of these problem families. The survey reveals the increasi...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2023
|
| Online Access: | https://hdl.handle.net/1721.1/151451 |
| _version_ | 1826210800525639680 |
|---|---|
| author | Rome, Hayden |
| author2 | Thompson, Neil |
| author_facet | Thompson, Neil Rome, Hayden |
| author_sort | Rome, Hayden |
| collection | MIT |
| description | This paper presents the first broad survey of the space complexities of algorithms for important problems in computer science, analyzing more than 800 algorithms for different problem families, and comparing the different algorithms for each of these problem families. The survey reveals the increasing importance of space complexity in recent years and discusses its relationship with time complexity. Our findings reveal an increasing trend in the percentage of algorithm papers that include space complexity analysis. We identify an increasing trend in the percentage of problem families with asymptotic time-space tradeoffs. Additionally, we find that the few problem families that see improvements in space complexity have typically improved at rates faster than the improvement rates of DRAM access speed and DRAM capacity. Under the right conditions, these algorithmic improvements to space complexity can be much more important than hardware improvements when considering computational speedups related to data accesses. This study sheds light on the space complexity of algorithms and contributes to a better understanding of the relationship between time and space complexities. We have also uploaded the space complexity work for this paper to our website, The Algorithm Wiki¹, to serve as a useful resource for theorists and practitioners alike. |
| first_indexed | 2024-09-23T14:55:57Z |
| format | Thesis |
| id | mit-1721.1/151451 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T14:55:57Z |
| publishDate | 2023 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1514512023-08-01T03:18:22Z The Space Race: Progress in Algorithm Space Complexity Rome, Hayden Thompson, Neil Lynch, Jayson Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science This paper presents the first broad survey of the space complexities of algorithms for important problems in computer science, analyzing more than 800 algorithms for different problem families, and comparing the different algorithms for each of these problem families. The survey reveals the increasing importance of space complexity in recent years and discusses its relationship with time complexity. Our findings reveal an increasing trend in the percentage of algorithm papers that include space complexity analysis. We identify an increasing trend in the percentage of problem families with asymptotic time-space tradeoffs. Additionally, we find that the few problem families that see improvements in space complexity have typically improved at rates faster than the improvement rates of DRAM access speed and DRAM capacity. Under the right conditions, these algorithmic improvements to space complexity can be much more important than hardware improvements when considering computational speedups related to data accesses. This study sheds light on the space complexity of algorithms and contributes to a better understanding of the relationship between time and space complexities. We have also uploaded the space complexity work for this paper to our website, The Algorithm Wiki¹, to serve as a useful resource for theorists and practitioners alike. M.Eng. 2023-07-31T19:40:48Z 2023-07-31T19:40:48Z 2023-06 2023-06-06T16:35:41.478Z Thesis https://hdl.handle.net/1721.1/151451 In Copyright - Educational Use Permitted Copyright retained by author(s) https://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Rome, Hayden The Space Race: Progress in Algorithm Space Complexity |
| title | The Space Race: Progress in Algorithm Space Complexity |
| title_full | The Space Race: Progress in Algorithm Space Complexity |
| title_fullStr | The Space Race: Progress in Algorithm Space Complexity |
| title_full_unstemmed | The Space Race: Progress in Algorithm Space Complexity |
| title_short | The Space Race: Progress in Algorithm Space Complexity |
| title_sort | space race progress in algorithm space complexity |
| url | https://hdl.handle.net/1721.1/151451 |
| work_keys_str_mv | AT romehayden thespaceraceprogressinalgorithmspacecomplexity AT romehayden spaceraceprogressinalgorithmspacecomplexity |