Hi everyone, I need your help in finding resources focusing on standard tasks/algorithms/data structures working with external memory. -> the model we use in our OI (that's the reason I need them) is described below. Unfortunately, I couldn't find much on the internet. In case you have any lecture notes / other resources you can share, I would be grateful.
Description of used external memory model : We have memory and disk. Working with a disk is much slower than working with memory. In the disk, data is stored in blocks of size b. The size of the disk is unlimited. When we work with the disk, we can perform 2 operations. Read / Write a block. The memory can store only a constant number of blocks at a time and thus we have to effectively use the disk to perform some given task.
Analysis of algorithms in this model : We analyze algorithms in terms of standard time complexity — the number of operations performed by our program (We can consider reads / writes O(1) or O(b) ). Then we have communication complexity (I'm not sure it's actually called that way). This complexity expressed the number of reads / writes performed by our algorithm. Both of these complexities are in terms of some input variables and b. For example, scanning through an array of size n has time complexity O(n) and communication complexity O(n/b).
