<p>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.</p>

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

CC BY-SA 4.0
2019-07-09T18:25:02.390Z
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.
Peeyush Kushwaha
CC BY-SA 4.0
2019-07-07T21:54:09.680Z
2019-07-07T21:54:09.680Z
jbapple
<p>I'm following course material from the course <a href="https://courses.csail.mit.edu/6.851/fall17/lectures/" rel="nofollow noreferrer">Advanced Data Structures</a>.</p>

<p>The result by Driscoll et al 1989 states the following (wording of the following theorem taken from <a href="https://courses.csail.mit.edu/6.851/fall17/lectures/L01.pdf" rel="nofollow noreferrer">lec notes, page 4</a>, which cites the original paper <a href="https://www.cs.cmu.edu/~sleator/papers/another-persistence.pdf" rel="nofollow noreferrer">"Making data structures persistent"</a>)</p>

<blockquote>
  <p>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</p>
</blockquote>

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

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

<p>So in summary, the backpointer update guarantees efficient reads. </p>

<p>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?</p>

CC BY-SA 4.0
2019-06-18T13:09:30.450Z
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.
Emil Jeřábek
CC BY-SA 4.0
2019-06-18T20:09:10.610Z
@EmilJeřábek thanks for the tip, first time on cstheoy :) updated the question.
Peeyush Kushwaha
<ds.data-structures>
Partially persistent linked list data structure: would lookup of the first element at a specific version be O(|versions|) and not O(1)?
Peeyush Kushwaha
# Partially persistent linked list data structure: would lookup of the first element at a specific version be O(|versions|) and not O(1)?

(Asked by: username_0 on 2019-06-11)

I'm following course material from the course [Advanced Data Structures](https://courses.csail.mit.edu/6.851/fall17/lectures/).

The result by Driscoll et al 1989 states the following (wording of the following theorem taken from [lec notes, page 4](https://courses.csail.mit.edu/6.851/fall17/lectures/L01.pdf), which cites the original paper ["Making data structures persistent"](https://www.cs.cmu.edu/~sleator/papers/another-persistence.pdf))

> 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?

**Tags:** ds.data-structures
> **Comments:**
> **username_1**: 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.  
> **username_0**: @EmilJeřábek thanks for the tip, first time on cstheoy :) updated the question.  

---

## 1 answers

### Answer by username_2 on 2019-07-07. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  

---

