You could do this with O(N^1/K) for arbitrary K, using K layers of indirection, no?
This is similar to how you can do O(logN) for insertion / deletion & access using an indexed B-tree, except you're using a fixed height instead of a fixed branching factor.
True. If you go k levels deep you get indexing complexity of O(k) (because you do a constant time operation for each level) and insertion/removal complexity of O(k + n^(1/k)) (because that’s indexing plus a linear insert/remove operation for the array at the bottom). If you push k towards log n you get O(log n) for both. (I’m ignoring rebalancing issues here but these can be dealt with too)
The article did mention that you can push k to values larger than 2 in the Generalization section. I think it would’ve been nice if they had explored such values when doing the performance tests, but either way I found it clear and nicely written.
for insert/remove you also need to move the last element up for each deque with higher indices, and If I understand it correctly, there should be O(N^(2/3)) (i.e. N^1/3 * N^1/3) such deques.
This is similar to how you can do O(logN) for insertion / deletion & access using an indexed B-tree, except you're using a fixed height instead of a fixed branching factor.