Questions tagged [constant-time]
The constant-time tag has no usage guidance.
10
questions
2
votes
1
answer
118
views
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.
...
- 603
1
vote
1
answer
126
views
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 ...
- 157
6
votes
3
answers
5k
views
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 ...
- 207
0
votes
1
answer
2k
views
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,...
- 519
0
votes
2
answers
183
views
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 ...
- 11
9
votes
2
answers
486
views
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 ...
- 690
1
vote
2
answers
5k
views
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 ...
user35756
6
votes
1
answer
834
views
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 ...
- 162
2
votes
1
answer
52
views
"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 ...
- 12.2k
3
votes
1
answer
155
views
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. ...
- 1,989