Space Complexity

Creator
Creator
Seonglae Cho
Created
Created
2021 Apr 29 4:40
Editor
Edited
Edited
2025 Jul 6 1:30
Refs
Refs
is actually effects
Time Complexity
because of assignment
exponential dependency on value because of bit representation
 
 
 
 
 
 
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.
 
 

Backlinks

Big O

Recommendations