It seems intuitive that there's no list data structure which has $\mathcal{O}(1)$ worst case time complexity for random access and a worst case complexity better than $\mathcal{O}(n)$ for insertion: if insertion is allowed to affect only a small part of the list, then there's no way for it to always keep the entire list in a structure that allows for constant time element access.

Is there any proof (or counterexample) of this?

  • 2
    $\begingroup$ When you say "insertion", what do you mean? Insertion at a specific index? $\endgroup$ – orlp Dec 5 '18 at 6:39
  • $\begingroup$ @orlp Yes, insertion at a specific index. $\endgroup$ – Stefan Dec 5 '18 at 6:40
  • 2
    $\begingroup$ In which computation model? This is important, because in real world if you keep connecting more and more memory to your computer (as big-Oh assumes), you can't expect constant-time random access to the memory. $\endgroup$ – Dmitri Urbanowicz Dec 5 '18 at 8:41
  • $\begingroup$ @DmitriUrbanowicz If you don't allow constant-time random access, you're just never gonna get O(1) here, so that's a bit ridiculous. Of course OP assumes random access. $\endgroup$ – Pål GD Jan 5 '19 at 9:19
  • $\begingroup$ Do you have to have O(1) worst case, or is O(1) amortized acceptable? $\endgroup$ – Pål GD Jan 5 '19 at 9:20

Yes, you can have both as fast as possible random access and faster-than-full-rebuild insertion time.

I assume you know how dynamically growing arrays work. Also, I assume you know how to make them work in $O(1)$ worst-case. These techniques allow us to focus on the problem for lists of limited size only.

Let $n$ be the maximal size (capacity) of the list. Let’s divide the list into $O(\sqrt{n})$ blocks of equal size $B$ (which is $O(\sqrt{n})$ too). Let also $b_j$ denote a cyclic shift of the $j$-th block.

When you need to access $i$-th element of the list, you calculate its position as follows in $O(1)$:

$$f(i) = (b_j + i \mod B) + B \times j$$

where $j = \lfloor \frac{i}{B} \rfloor$.

When you need to insert something into $i$-th position, you first make a cyclic shift of everything from $j$-th block to the end:

  1. Decrement all $b$ values starting from $j$.
  2. Swap the elements on the boundaries of consequtive blocks, so that every element is in its right place.
  3. Then you fix $j$-th block by rebuilding it from scratch.

This gives you $O(\sqrt{n})$ insertion complexity.

| cite | improve this answer | |

As accessing to an element is in $O(1)$, it would be something like an array. And, if this assumption is true, your discussion would be near the concept of "Dynamic Array". It's insertion to the array is $O(1)$ and amortized cost of $n$ insertion to the data structure is $O(n)$. It might be helpful for what you want to reach.

| cite | improve this answer | |
  • $\begingroup$ I didn't downvote you, and don't know who did, but inserting into the beginning or to the middle in a dynamic array is O(n). Inserting at end is amortized O(1). I think OP wanted arbitrary insert to be (amortized?) O(1). $\endgroup$ – Pål GD Jan 5 '19 at 9:17

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.