Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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:
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.
