2022 Developer Survey is open! Take survey.
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
3 votes
Accepted

Find the smallest difference between two numbers in a DS in O(1) time

Use an AVL tree with each node having three additional entries $\min,\; \max$, and $\text{closest_pair} = (i,j)$, representing the minimum and maximum values of the tree rooted at that node. At the ...
user avatar
3 votes
Accepted

Shortest word not in dynamic set

Link shorteners don't face this problem. When they generate a word for you, they use a fixed-length words, so it suffices to keep a dictionary of all words that are currently in use. Also most words ...
user avatar
  • 140k
2 votes
Accepted

Randomized Algorithm Lemma

To prove the claim $$ P(Mr = 0 ) \leq \frac{1}{2} $$ it is enough to prove it for any row vector $m = (M_{i,1},...,M_{i,n})$ that has at least one non-zero coefficient. Thus, we continue by induction ...
user avatar
2 votes

equivalency of some facts in $O$ notation

Let $a>b>0$. From $\log(a+b)=\log(a)+\log\left(1+\dfrac ba\right)$, we draw $$\log(a)\le\log(a+b)\le \log(a)+\log(2)$$ and similarly for $b>a$.
user avatar
  • 3,337
1 vote

Find the smallest difference between two numbers in a DS in O(1) time

I'm assuming that the sets of functions in big-Oh notation refer to the desired worst-case time complexity of the operations. A possible data structure consists of an AVL tree $T$ plus a priority ...
user avatar
  • 22.7k
1 vote

Find the smallest difference between two numbers in a DS in O(1) time

I think this can be done using $(a,b)$-trees storing a bit more information in internal nodes: the minimum difference between two leaves in the subtree; the minimum and maximum values of a leaf in ...
user avatar
  • 7,154
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

Only top scored, non community-wiki answers of a minimum length are eligible