common implementation of sequential files on disk has each block point to its successor, which may be any block on the disk. This method requires a constant amount of time to write a block (as the file is originally written), to read the first block in the file, and to read the ith block, once you have read the 1 - 1” block. Reading the lth block therefore requires time proportional to 1. Show how by adding just one additional pointer per node, you can keep all the other properties, but allow the lth block to be read in time proportional to log I. [Hint: heaps have implicit pointers from node I to what other nodes?] Explain what the algorithm for reading the th block has in common with an algorithm for raising a number to the ith power in time proportional to log 1.
A common implementation of sequential files on disk has each block point to its successor, which may be any block on the disk. This method requires a constant amount of time to write a block (as the file is originally written), to read the first block in the file, and to read the ith block, once you have read the 1 - 1” block. Reading the lth block therefore requires time proportional to 1. Show how by adding just one additional pointer per node, you can keep all the other properties, but allow the lth block to be read in time proportional to log I. [Hint: heaps have implicit pointers from node I to what other nodes?] Explain what the
Step by step
Solved in 2 steps