{"ID":5439534,"CreatedAt":"2026-07-01T01:17:58.482524686Z","UpdatedAt":"2026-07-07T03:14:33.014478982Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.30948","arxiv_id":"2606.30948","title":"The Fourth-Root Complexity of Data Movement","abstract":"Time complexity typically assumes $O(1)$ cost per data access. This paper presents an analysis based on an abstract memory hierarchy. For a common class of applications, it shows that the data-access cost scales with the fourth root of data size, that is, as data size $N$ increases, the cost of each access increases at the rate of $N^\\frac{1}{4}$. While the analysis does not predict performance, it predicts scalability. Specifically, the paper provides a precise analysis that shows the constant-factor difference between cases where the miss ratio follows a power law versus an exponential decay.","short_abstract":"Time complexity typically assumes $O(1)$ cost per data access. This paper presents an analysis based on an abstract memory hierarchy. For a common class of applications, it shows that the data-access cost scales with the fourth root of data size, that is, as data size $N$ increases, the cost of each access increases at...","url_abs":"https://arxiv.org/abs/2606.30948","url_pdf":"https://arxiv.org/pdf/2606.30948v1","authors":"[\"Chen Ding\"]","published":"2026-06-29T22:01:50Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.PF\",\"cs.PL\"]","methods":"[]","has_code":false}