Can a list with $\mathcal{O}(1)$ access have an insertion complexity better than $\mathcal{O}(n)$?

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?

• When you say "insertion", what do you mean? Insertion at a specific index? – orlp Dec 5 '18 at 6:39
• @orlp Yes, insertion at a specific index. – Stefan Dec 5 '18 at 6:40
• 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. – Dmitri Urbanowicz Dec 5 '18 at 8:41
• @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. – Pål GD Jan 5 at 9:19
• Do you have to have O(1) worst case, or is O(1) amortized acceptable? – Pål GD Jan 5 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.

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.

• 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). – Pål GD Jan 5 at 9:17