I'm interested in lower bounds on the amortized time cost for either of the following dynamic data structure problems, in the cell probe or RAM model, or any model that lets us do operations on words in constant time. There shouldn't be any restriction on the size of uninitialized memory that you're allowed to index into.
For both problems, i is a log n bit word, and I'm fine with assuming that x is also a word.
Data structure 1
- insert(i,x) : insert x at position i in the list
- get(i) : return the i-th element of the list
Data structure 2
- add(x) : add x to the set
- getByRank(i) : return the i-th largest element in the set
For both problems, log n / log log n seems like an upper bound using trees of branching factor sqrt(log n), but I haven't worked that out carefully at all.
I have read Lower Bounds for Data Structures, and I'm aware of the lower bounds for prefix sum (see e.g. https://cstheory.stackexchange.com/a/21575/28706 or lecture notes http://www.tcs.tifr.res.in/~prahladh/teaching/2011-12/comm/lectures/l21.pdf or https://arxiv.org/pdf/cs/0502041.pdf). I don't see how to use the prefix sum result, and the other results I could find are all for data structures that support a delete operation.
I admit I have not studied the lower bound proofs... so forgive me if either of these problems are simple adaptations.
Note: the 2005 arXiv paper I linked to above might imply a lower bound of log n / log log n for the following related, but harder, problem, which adds a third operation:
- add(x) : same as in data structure 1 above
- getByRank(i) : same as in data structure 1 above
- rank(x) : return the rank (ordinal) of x, where x was previously added.
