Second addendum:  Considering that the new algorithm is a time-space tradeoff, it is also worth stating the main result in a generalized form with unequal sizes for the two types of Gauss subdiagrams, so that you can partially trade time for space.  This is the correct theoretical statement of the complexity of the algorithm.  It also reflects the practical concern that in a large computation, you might well run out of computer memory before you run out of computer time.