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

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.