memory management and -trees caching strategies the significance of the memory hierarchy on the performance of program depends greatly upon the size of the problem we are trying to solve and the physical characteristics of the computer system oftenthe bottleneck occurs between two levels of the memory hierarchy--the one that can hold all data items and the level just below that one for problem that can fit entirely in main memorythe two most important levels are the cache memory and the internal memory access times for internal memory can be as much as to times longer than those for cache memory it is desirablethereforeto be able to perform most memory accesses in cache memory for problem that does not fit entirely in main memoryon the other handthe two most important levels are the internal memory and the external memory here the differences are even more dramaticfor access times for disksthe usual general-purpose external-memory deviceare typically as much as to times longer than those for internal memory to put this latter figure into perspectiveimagine there is student in baltimore who wants to send request-for-money message to his parents in chicago if the student sends his parents an email messageit can arrive at their home computer in about five seconds think of this mode of communication as corresponding to an internal-memory access by cpu mode of communication corresponding to an external-memory access that is times slower would be for the student to walk to chicago and deliver his message in personwhich would take about month if he can average miles per day thuswe should make as few accesses to external memory as possible most algorithms are not designed with the memory hierarchy in mindin spite of the great variance between access times for the different levels indeedall of the algorithm analyses described in this book so far have assumed that all memory accesses are equal this assumption might seemat firstto be great oversight-and one we are only addressing now in the final -but there are good reasons why it is actually reasonable assumption to make one justification for this assumption is that it is often necessary to assume that all memory accesses take the same amount of timesince specific device-dependent information about memory sizes is often hard to come by in factinformation about memory size may be difficult to get for examplea python program that is designed to run on many different computer platforms cannot easily be defined in terms of specific computer architecture configuration we can certainly use architecture-specific informationif we have it (and we will show how to exploit such information later in this but once we have optimized our software for certain architecture configurationour software will no longer be deviceindependent fortunatelysuch optimizations are not always necessaryprimarily because of the second justification for the equal-time memory-access assumption