Seonglae ChoTime 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.
Memory access is due to physical constraints (geometry + signal propagation) for fundamental scaling law.
When a CPU directly accesses the entire memory, access time (latency) is proportional to the distance the signal travels, and storage capacity N is proportional to volume in three-dimensional space. This means that simply making tables larger isn't optimal even with sufficient memory; instead, optimal performance requires balancing cache hit rates and latency.