[jbapple]

Assuming you ignore the constant. And if you're willing to ignore the constant, you can get O(c) access, O(N^(1/c)) insert and delete at arbitrary indices, and O(c) insert at head and tail, for any constant c. The trick is to make the array into a B-tree of width N^(1/c) and depth c. Note that the insert/delete time is amortized: the worst-case time is O(cN^(1/c)).

[zawerf]

Yea someone else also mentioned that generalization (called a tiered vector) in that thread: https://news.ycombinator.com/item?id=20873110