1.8. Space Complexity Considerations

So, about space complexity, we said that we are going to represent each W0, W1, etc., as one coordinate. So, we have basically n times n times n, because we have n times n as the actual matrix, and we have n of these matrices, because we have level 0, level 1, and level n. But we say that in our worked-out example, that when you need to compute level 1, we only need level 0, then we can throw away level 0. When we need to compute level 2, you need only level 1.

The explanation of space complexity revolves around the memory used to store the data structures of the algorithm. In the Floyd-Warshall algorithm, initially, you would think that we require a three-dimensional matrix to store all combinations of vertices at each level, resulting in O(n^3) space complexity. However, since each iteration relies only on the previous iteration, you can optimize this by utilizing only two matrices at any time—keeping the most current data and the previous data. Thus, instead of needing O(n^3) space, you only need 2 * O(n^2), effectively optimizing your requirements.

Think of it like organizing your files in a filing cabinet. Imagine you have a cabinet with three drawers (representing the three levels of W0, W1, W2, ...). If each drawer can only hold the previous drawer's files plus new ones, you don’t need to keep all three drawers full at the same time; you can cycle between two drawers, just like using two levels of your matrix. This way, you save space while still having access to all necessary information.

So, in some sense, you can keep only 2 copies and keep switching back and forth. You overwrite the zeroth level as the second level, you overwrite the first level as the third level, and so on. So, we need only 2 slices of this three-dimensional matrix at a time.

The crux of this chunk is about memory efficiency. Since you only need the results of the last two states to compute the next state, you can overwrite earlier results. When you create a new version of the results at level k, you only look back at level k-1 and don’t actually need the previous states anymore. This method of alternating between two matrices continues while processing all vertices, which streamlines memory usage significantly.

Imagine you're baking cookies and continually testing the dough’s taste after each batch. Instead of writing down every dough recipe you create (which would take a lot of space), you just keep one notebook open, always revising the last one you made. This method of working lets you save paper while still keeping track of your best cookie dough!

So just an observation that in this particular thing, you do not really need to have the n cubed array; you can have a 2n squared array or an n squared array with two indices and keep oscillating between the two and get the same effect, because you only need one copy to compute the other copy.

This part emphasizes the clever use of array size as a fundamental aspect of efficient programming. Instead of allocating a large O(n^3) space for all possible combinations of vertex paths, you can achieve the same results leveraging the limited data needed for computations. By using fewer resources effectively, you can improve program efficiency and run time.

Think of packing for a trip. Instead of taking a large suitcase that can fit everything you might need (which is heavy and cumbersome), you choose to take a smaller bag and only the essentials—things you really know you’ll use. This not only makes your travel easier but allows you to be efficient with your packing, much like optimizing space in your algorithm.

--