Thank you @eksperimental for tagging me. What an interesting topic!
Yes and no. The Erlang :array module indeed does not state a particular time complexity and it is allowed to change its internal implementation whenever a new version of Erlang would want.
But practically speaking, for the last 15+ years, the implementation has been the same: finger trees with node size 10 (in other words: nested 10-element-tuples), meaning that access is O(log10(n)). Logarithmic time complexities (especially those with large bases) can be considered ‘practically constant-time’.
Besides my Arrays library there’s also Okasaki which is very similar but for queues. It probably will have a constant-time overhead over using :queue directly because of the extra layer of wrapping with Elixir structs and protocols, but using it should be much more idiomatic than using :queue or :array directly.
And then there are of course a hand full of libraries written using NIFs (natively implemented functions), such as Explorer and Nx which are faster for certain math or data science operations (when you want run the same calculation on a large block of data) but they are not general-purpose (you cannot store any Elixir structure in them; most operations only work on ints or floats).
I might try to write an implementation of this example problem myself if I find the time 
.
