The Fourth-Root Complexity of Data Movement

Chen Ding

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 t…