Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I know that retrieving an item in a collection can be done in $O(1)$ time(on average) using hash tables. I would like to know if there is an algorithm that could be as performance without using arrays.
My main motivation for this question is to know if it is possible to build a retrieve element algorithm in $O(1)$ time using just functional programming. It seems that the lower bound is $\Omega(\log(n))$ using trees $T = (a, (T, T)) \text{ | ( )}$.
Without arrays, $\Omega(\log n)$ time is needed. Without arrays, the memory address you access is entirely determined by the control-flow path, i.e., the sequence of control-flow decisions (if construed appropriately) made during the execution. At each step, you can only choose between one of two (or a fixed finite number) of choices for control-flow. So, after $t$ steps of execution, there can be at most $O(2^t)$ different control-flow paths, and at most $O(2^t)$ different memory positions that could potentially be accessed. For the data structure operation to be correct, it needs to be possible to access every one of the $n$ memory positions, so you basically need $2^t \ge n$, which means you need $t \ge \log n$.
@D.W. what if at each step, there is not a fixed finite number of choices, rather some $k$ choices. In that case, there would be $O(k^t)$ different control-flow paths. By properly tuning, $k$ and $t$ , we can get $t^t \geq n$ or $t \geq W(n)$. Here $k$ is Lambert's W-function. @D.W. I think a little more explanation is needed why this cannot happen.
In my opinion, the logic is lying inside the register level. A processor should be able to map the entire range of $n$ different memory units (not necessary RAM units). Considering binary representation there is no way out to hold information of $n$ different locations lesser than $\log_2(n)$ bits. While we are talking in terms of an array, or considering hash-table can access data in $O(1)$ average time, we assume hash operation is performed in $O(1)$ time. In reality, for hash operation, it takes at least $O(\log_2(n))$ time (considering the processing of a bit or a constant number of bits at a time). This book is focusing a bit on these aspects.
