This note relates to the paper
The space reported in Table 1 is not peak memory usage during search time for method `Sada`. It is an estimate, assuming a space-optimal implementation of the $2n+o(n)$-bit range minimum query data structures. The actual memory usage for Sada is about two times larger.
Thanks to Simon Gog for spotting this discrepency, and writing the text of this note.
Page created by Andrew Turpin Wed 16 Apr 2014 13:31:00 EST