I&C SCI 46 Lecture Notes - Lecture 29: Pseudocode, Complexity Class

• School: UC-Irvine
• Department: Information and Computer Science
• Course: I&C SCI 46
• Professor: Richard Pattis

Document Summary

B-trees: an efficient structure for searching data on external memory. In this lecture we will examine one data structure and algorithm that is useful when storing the data needs more space than is available in main memory. We will analyze this algorithm with respect to how often it moves blocks of data between main and external memory (discussed in the previous lecture). Typically the cost of such memory transfers dominates the cost of executing code on the block while it is in memory. That is, a transfer between main and external memory might take 10 milliseconds, while processing the data in the block might take microseconds (a few 1/1000ths of a millisecond) before making another memory transfer. A processor executing 10^9 instructions per second can process 10^7 (10 million) instructions in 10 ms. So, we can virtually ignore the time taken to process each block retrieved from memory, counting only the number of transfers.