시간 복잡도 (Time complexity)는 일반적으로 데이터 접근당 $O(1)$의 비용을 가정합니다. 본 논문은 추상적인 메모리 계층 구조 (memory hierarchy)를 기반으로 한 분석을 제시합니다. 일반적인 애플리케이션 클래스의 경우, 데이터 접근 비용이 데이터 크기의 4제곱근에 따라 확장됨을 보여줍니다. 즉, 데이터 크기 $N$이 증가함에 따라 각 접근 비용은 $N^rac{1}{4}$의 비율로 증가합니다. 이 분석이 성능을 예측하지는 않지만, 확장성 (scalability)을 예측합니다. 구체적으로, 본 논문은 미스 비율 (miss ratio)이 멱법칙 (power law)을 따르는 경우와 지수적 감소 (exponential decay)를 따르는 경우 사이의 상수 계수 차이를 보여주는 정밀한 분석을 제공합니다.