0
$\begingroup$

I'm following course material from the course Advanced Data Structures.

The result by Driscoll et al 1989 states the following (wording of the following theorem taken from lec notes, page 4, which cites the original paper "Making data structures persistent")

Any pointer-machine data structure with O(1) pointers to any node can be made partially persistent with O(1) ammortized multiplicative overhead and O(1) space per change

I understand the argument for why reads are O(1). The key idea is that during a write to n when a new node n' is created due to mod table overflow, we guarantee existence of a mod entry pointing to n' in any node x which has a field pointing to n.

During a read, you can look at appropriate mod entry in x which will point to either n or n' depending on the version, so you only have to look at O(mod table size) entries at every read.

So in summary, the backpointer update guarantees efficient reads.

However, in my program I start out with a pointer to the head of the linked list in a variable. With backpointer updates, it'll always point to the latest version. Which means that if I have to look up an older version of the list, I'll have to go through all mod tables of the first node of the linked list till I arrive at the correct version, making it O(n) in number of versions and not O(1). Is that correct?

$\endgroup$

migrated from cs.stackexchange.com Jun 18 at 12:23

This question came from our site for students, researchers and practitioners of computer science.

  • 1
    $\begingroup$ You should include a proper reference to the paper (title, authors, journal name, volume, pages, etc). Otherwise no one has an idea what you are talking about. $\endgroup$ – Emil Jeřábek Jun 18 at 13:09
  • $\begingroup$ @EmilJeřábek thanks for the tip, first time on cstheoy :) updated the question. $\endgroup$ – Peeyush Kushwaha Jun 18 at 20:09
1
$\begingroup$

I think this is really a question about the API features. Access to an older version, in Driscoll et al.'s sense, requires a pointer to that version, not just a predicate used to traverse a version tree to locate the version.

For a similar API/modelling question, you can look at the question of how long delete takes in a priority queue. Plenty of papers advertise that they offer $O(1)$ delete, but this assumes one already has a pointer to the item to be deleted.

$\endgroup$
  • $\begingroup$ That makes sense to me. I was just checking my understanding because it claimed to be $O(1)$ but I could think of a way it wouldn't be. This answer confirms that that it's right and I'm also right, so thanks. $\endgroup$ – Peeyush Kushwaha Jul 9 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.