New answers tagged lower-bounds
0
votes
How to evaluate the tightness of a bound on a function?
To evaluate tightness of a bound on a function, you need to find both the upper and lower bounds. Finding an upper bound on the function is good but it leaves the possibility that the actual function ...
1
vote
What is the lower bound on retrieving an item in a collection if no arrays(Random access memory) are allowed?
@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$ ,...
5
votes
Accepted
What is the lower bound on retrieving an item in a collection if no arrays(Random access memory) are allowed?
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 ...

D.W.♦
- 140k
Top 50 recent answers are included
Related Tags
lower-bounds × 231complexity-theory × 78
algorithms × 75
time-complexity × 36
sorting × 34
graphs × 18
algorithm-analysis × 18
upper-bound × 15
asymptotics × 14
proof-techniques × 14
circuits × 14
data-structures × 12
arrays × 12
space-complexity × 10
decision-tree × 8
runtime-analysis × 7
information-theory × 7
reference-request × 6
computational-geometry × 6
communication-complexity × 6
turing-machines × 5
optimization × 5
matrices × 5
finite-automata × 4
np-complete × 4