Time Complexity

Creator
Creator
Seonglae Cho
Created
Created
2021 Apr 29 4:40
Editor
Edited
Edited
2025 Jul 6 1:30
Time Complexities
 
 
Time Complexity Notion
 
 
 
A new proof overturns the assumption that 'computing in time t requires about t bits of memory,' showing that all problems solvable in time t need only about √t bits of memory. This is achieved by efficiently reusing space through problem transformations (reductions).
In other words, this insight suggests that how wisely you use space is more important than computational time.
 
 

Recommendations