# Questions tagged [definitions]

The tag has no usage guidance.

9 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
95 views

### Understanding the Transition points of a BST

I'm trying to understand the definition of Transition point of a BST, as given in Demaine, Erik D., et al. "Dynamic optimality-almost." SIAM Journal on Computing 37.1 (2007): 240-251 ...
51 views

### What is the name of visiting an array starting at first element, then last element, then second, then last but one, then third, etc

For example if I have an array [0, 1, 2, 3, 4, ..., n] and I want to iterate over it in an order like ...
• 161
50 views

### Regarding the definitions of time-constructible functions on Wikipedia

I am reading the Wikipedia article on time-constructible functions and got confused by its definitions, given as follows: There are two different definitions of a time-constructible function. In the ...
• 457
1 vote
49 views

### Language of all words of the form $ww$ is in $\mathsf{NTIME}(n)$

Show that the language $\{ ww \mid w \in \{0,1\}^* \}$ is in $\mathsf{NTIME}(n)$. I have a doubt first of all how can I prove that. Secondly, what does NTIME mean? Can we use a $k$-Tape Turing ...
1 vote
43 views

### A genral Turing model with one tape to define sublinear space (L,NL,..)

A genral Turing model with one tape to define sublinear space (L,NL,..) Normally to define sub-linear space complexity we need special Turing models with many tapes, at least two: a read-only tape and ...
• 243
1 vote
45 views

### Randomized version of the class $APX$?

Is there a class which is to APX what BPP is to P? I'm looking for a definition that is like the following: "For $r > 0$, an $r$-RPCA (randomized polynomial-time constant-factor approximation) ...
• 374
21 views

### Why do the authors use the 'trigraph' to characterize some class of graphs?

I have read the series of papers about "the structure of claw-free graphs" (https://doi.org/10.1016/j.jctb.2008.03.002). Here the authors used the trigraph, that is the adjacency relation ...
172 views

### Definition of the term "access efficiency" in the context of computer systems

In a two-level virtual memory, the memory access time for main memory, $t_M=10^{−8}$ sec, and the memory access time for the secondary memory, $t_D=10^{−3}$ sec. What must be the hit ratio, $H$ such ...
• 1,142