Questions tagged [constant-time]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
3 answers

Element that occurs more than one third of the time in a sorted array - constant time?

Given a sorted array of positive integers that is guaranteed to have some unique entry that occupies more than $1/3$ of the entries, is there an algorithm to determine this entry in $O(1)$ time? Some ...
user165069's user avatar
0 votes
0 answers

How do Turing machines output $f(w)$ for $O(1)$ reductions?

When speaking about many-one Karp reductions, the definition is stated below: $$ A \leq_P B \iff \exists f \colon \: \Sigma^* \mapsto \Gamma^* \: \text{such that} \: (w \in A \iff f(w) \in B) $$ where ...
Ank i zle's user avatar
  • 153
3 votes
0 answers

Are any known problems complete for $P$ under "$O(1)$ reductions?"

The usual many-one reduction involves Turing machines transforming an input, $w$, of some language to an input, $f(w)$, of some other language in polynomial time. (Where $w \in L_1 \iff f(w) \in L_2$)....
Ank i zle's user avatar
  • 153
2 votes
1 answer

Sorted list of counters in constant time

Summary. A data structure maintains in constant time a sorted list of counter values, for a dynamic set of counters. I am interested in references using this structure, and in possible improvements. ...
Matthieu Latapy's user avatar
1 vote
1 answer

Finding the Range of Solutions for KSum Variation

Preface I asked a question before where I was looking to understand the complexity class of the following problem: Given a range of integers $\{a,a+1,...,b-1,b\}$, find a subset of size $k$ such ...
tkellehe's user avatar
  • 157
6 votes
3 answers

Is It Possible For a Data Structure to Have Constant Time Access/Insertion/Deletion?

I'm trying to come up with a data structure that could access, insert, and delete any element in constant time. I know that's pretty difficult, but I'm just doing it to invoke thought and ...
Badr B's user avatar
  • 207
0 votes
1 answer

What are some constant time operations? [closed]

I know that some operations are definitely constant time, such as accessing an item in a list, however there are other operations that are assumed constant time sometimes, but non-constant other times,...
wjmccann's user avatar
  • 549
0 votes
2 answers

Interview question (constant-time algorithm, ILP)

A juice machine has three buttons small, medium large. Each size adds an amount of juice in a range to the cup. Eg small might add from 10-20 mL, medium from 30-35 mL, large from 40-50 mL. The exact ...
s n's user avatar
  • 11
10 votes
2 answers

Do there exist "O(1)-complete" problems?

Many complexity classes have "complete" problems. Do complete problems exist for the complexity class of problems that can be solved in $O(1)$ time? A complication is that this class depends on the ...
Mike Battaglia's user avatar
2 votes
2 answers

Data structure with constant time operations

I need to use a data structure, implementable in C++, that can do basic operations, such as lookup, insertion and deletion, in constant time. I, however, also need to be able to find the maximum value ...
user avatar
6 votes
1 answer

Lower bound for finding majority element in a sorted array

Suppose $A$ is a sorted array with $n$ elements. I want to know whether we can determine if there are majority elements in $A$ with time complexity $O(1)$. Recall that a majority element of $A$ is ...
Paul's user avatar
  • 162
2 votes
1 answer

"Print 'em all game" for Turing machines

Suppose that we have a tape restricted to $n$ cells on binaryalphabet $\Sigma = \{0,1\}$ and initially filled with zeroes. We want to build a Turing machine $M_n$ (or better a Linear Bounded ...
Vor's user avatar
  • 12.5k
3 votes
1 answer

Simplest argument that language decidable in constant time cannot be $\mathsf{NP}$-hard?

My question is specifically about $\emptyset$, but more generally about any language that can be decided in (deterministic or nondeterministic doesn't really make a difference here) constant time. ...
G. Bach's user avatar
  • 2,019