2
$\begingroup$

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{ | ( )}$.

$\endgroup$
0

2 Answers 2

5
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

@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.

$\endgroup$
2
  • 2
    $\begingroup$ Please don't use answers to respond to other answers. Our site works differently from others you might be used to. We are not a discussion forum -- each answer must directly answer the question that was asked. If you would like to comment on or respond to another answer, you can leave a comment under that answer (once you have acquired enough reputation to offer you that privilege). $\endgroup$
    – D.W.
    May 3 at 18:22
  • $\begingroup$ Ok. I would keep that in mind in futute. $\endgroup$ May 4 at 1:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.