New answers tagged

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 ...
user avatar
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$ ,...
user avatar
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 ...
user avatar
  • 140k

Top 50 recent answers are included