How to avoid initializing memory [in theory]

Consider an algorithm that uses a large memory area. If the running time of the algorithm is smaller than the size of the memory, initializing the memory will take longer than running the algorithm. However, using a shrewd trick, it’s possible to refrain from initializing the memory.

This mysterious trick is used quite frequently in research articles, often without explanation and a reference to Exercise 2.12 in The Design and Analysis of Computer Algorithms by Aho, Hopcroft, and Ullman, 1974.

Develop a technique to initialize an entry of a matrix to zero the first time it is accessed, thereby eliminating the O(||V||2) time to initialize an adjacency matrix.

To add insult to injury, this exercise is marked with a single star, and it’s widely believed that the number of stars indicates the number of authors who couldn’t solve the problem either.

Can your figure it out?

Memory                         Active
-------------------------      -------
Address Contents Pointer

0       134431   X---------->  0
1       938434      -------->  4
2       432754      |  ----->  6
3       292343      |  |
4       874944   X---  |
5       002345         |
6       654243   X------
7       112903

Further reading

See The fastest sorting algorithm? for an O(n log log n) time sorting algorithm that uses this trick, and quite a few others.

Share: