Skip to main content

Questions tagged [definitions]

The tag has no usage guidance.

9 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4 votes
0 answers
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 ...
Margaret Bloom's user avatar
3 votes
0 answers
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 ...
Azat Ibrakov's user avatar
2 votes
0 answers
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 ...
3nondatur's user avatar
  • 457
1 vote
0 answers
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 ...
Aman Shaikh's user avatar
1 vote
0 answers
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 ...
rl1's user avatar
  • 243
1 vote
0 answers
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) ...
Elle Najt's user avatar
  • 374
0 votes
0 answers
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 ...
Hanchun Yuan's user avatar
0 votes
0 answers
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 ...
Abhishek Ghosh's user avatar
0 votes
0 answers
30 views

How isolate the last bit work on teory Binary Indexed Trees

I'm learning about the Binary Indexed Trees, and I understand how it works, but I'm interested in the theory that there is behind! In particular, I don't understand what is meant the following ...
macros's user avatar
  • 45