= Solution
\b[Not necessarily: <structural sharing> can make snapshots cheap, but the trait alone gives no storage guarantee.] With a <persistent data structure>, unchanged portions of old and new <sequences> can be shared safely. Saving two root references costs $O(1)$ additional space per edit, and adjacent history entries commonly refer to the same intermediate version. With an appropriate balanced persistent <tree>, each positional edit may add only $O(\log n)$ new <vertices>, giving approximately $O(n+h\log n)$ storage for $h$ retained edits of comparable presentation size, plus references to slides.
There are important qualifications. A fully copied immutable <array> may allocate $\Theta(n)$ per edit and use $\Theta(hn)$ across its history. A persistent <linked list> shares suffixes but may copy a long prefix for a late positional edit. Moreover, snapshot history keeps old versions alive that an edit-specific inverse representation might otherwise release. Consequently a significant increase is possible with some implementations or workloads; it is not forced by saving `Sequence` references, and it cannot be ruled out from the interface alone.
Back to article page
