Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

New answers tagged

3 votes
Accepted

Proving transitivity in an intuitionistic type theory without the K rule

$\newcommand{\J}{\mathsf{J}} \newcommand{\K}{\mathsf{K}} \newcommand{\refl}{\mathsf{refl}}$ Yes, this just uses axiom $\J$. $\K$ is only necessary for translating certain particular cases of pattern ...
user avatar
  • 2,050
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