Time Complexity of Piece Table and Rope

Question

I was reading about the data structures behind various text editors and had a couple of questions.

If I understand this correctly, searching/traversing on Piece Table is O(n) as you need to go through the linked list one by one, whereas Rope only requires O(logn) time as it is structured as a balanced binary tree.

Then how come in this stackoverflow answer and this IBM article, it claimed that "Insertion become nearly constant time operations" and "in most data-processing routines, sequential access to a rope's characters is what's required, in which case a rope iterator can provide amortized O(1) access speed". Am I missing something here? Shouldn't them all be O(logn) since they need to find the position of the leaf first?

All feedbacks/answers are welcomed! Cheers!

Maybe it is implied that you already have the leaf, and the position in the leaf. — Dialecticus, Jun 11 '17 at 08:29
@Dialecticus Maybe, but seems like stating the obvious in that case. — zokland, Jun 11 '17 at 21:27
Your question has at least seven questions. It has been my observation that posts with a single, focused question get more answers. — jbapple, Jun 11 '17 at 21:47

score 4 · Accepted Answer · answered Jun 14 '17 at 05:55

You asked two questions:

Q1. How can "insertion become nearly constant time operations"?

A1. Because some people believe that O(log n) is "nearly constant time". You might disagree with those people.

Q2. How can "sequential access to a rope's characters is what's required, in which case a rope iterator can provide amortized O(1) access speed"?

A2. Sequential access is different than search. You posited "searching/traversing on Piece Table is O(n) as you need to go through the linked list one by one, whereas Rope only requires O(logn) time", but that statement lumps together two operations (searching and traversing) that have different access costs.

Traversing a data structure always takes at least Ω(n) time, because you have to traverse each element. On the other hand, search can be O(1) for some data structures.

Now that we have that straightened out, let's examine the statement you question: what does "sequential access ... amortized O(1)" mean? It means that you can search for a given location and then traverse sequentially after it in O(1) amortized time. These bounds on balanced search trees are typically O(log n + k), where k is the number of items traversed. If k is Ω(log n), this is O(k), which is O(1) per item.

Time Complexity of Piece Table and Rope

1 Answers1