Best known (state of science) time complexity of an array access problem
-
05-11-2019 - |
Question
Consider an Array $A$ with $n$ values and the following operations:
- get(i): Returns the value of $A[i]$
- insert (x): Insert the element x into the any free place in A (not necessarily in $A[x]$ or the end of the array)
- delete (x) delete the element $A[x]$
What is the best known (amortized) time complexity of all operations? Especially the delete-op seems like it needs at least $\Omega(log n)$
See also the papers in this post. However the insert operation is defined slightly different by me, does this have any effect?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange