Questions tagged [time-complexity]
The amount of time resources (number of atomic operations or machine steps) required to solve a problem expressed in terms of input size. If your question concerns algorithm analysis, use the [runtime-analysis] tag instead. If your question concerns whether or not a computation will *ever* finish, use the [computability] tag instead. Time-complexity is perhaps the most important sub-topic of complexity theory.
1,898
questions
10
votes
3answers
970 views
Proving that if $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$
I'd really like your help with proving the following.
If $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$.
Here, $\mathrm{NTime}(n^{100})$ is the class of ...
5
votes
1answer
731 views
Double-nested loop with bitwise operation
I have this little exercise:
for ( i = 0; i < 2 * n; i += 2 )
for ( j = 1; j <= n; j <<= 1 )
if ( j & i )
foo ();
(...
2
votes
1answer
65 views
Advice speeds up computations
I want to show that reasonable advice can really speed up computation.
Show, that every time-constructible function $t$, there exists a set $S$ in time $\text{DTIME}(t^2) \setminus \text{DTIME}(t)$ ...
4
votes
2answers
539 views
Proof for P-complete is not closed under intersection
Unfortunately I have no idea how to show this:
Show that the set of ${\sf P}$-complete languages is not closed under intersection.
As far as I understand my lecture notes, ${\sf P}$-completeness ...
1
vote
1answer
1k views
Computational complexity of the clique problem
What is the best known approximation for the computational complexity of the clique problem? Is it accurate to consider it $O(2^n)$?
4
votes
1answer
3k views
Maximum Schedulable Set Zero-Lateness Deadline Scheduling
This is a homework problem for my introduction to algorithms course.
Recall the scheduling problem from Section 4.2 in which we sought to
minimize the maximum lateness. There are $n$ jobs, each ...
2
votes
1answer
124 views
determine if a machine prints a certain string in less time than it takes to run the machine itself?
Does there exist a procedure that determines if a polytime machine prints a certain string, and does so in less time than the machine itself takes to run?
Define a machine $a$ that analyzes another ...
3
votes
1answer
203 views
Notations around the polynomial hierarchy
I am new to "Computational Complexity" and therefore I have enough problems with some exercises like the following one:
Remember: $\text{PH} := \bigcup_{i} \Sigma_i$
Show:
$\bullet \...
7
votes
2answers
171 views
Two functions $g(n)$, $G(n)$ such that $g(n) = o(G(n))$ but $g(n+1) \neq o(G(n))$
The title of the question expresses what I'm looking for - this is to help me better understand the prerequisites for the Non-Deterministic Time Hierarchy Theorem
For instance, the Arora-Barak book ...
2
votes
1answer
114 views
Strict polynomial hierarchy and reduction
The following exercise gives me headaches:
Show: If the polynomial hierarchy is strict (i.e. $\forall k \in \mathbb{N}. \Sigma_k \neq \Sigma_{k+1}$), then there is no $\text{PH}$-complete problem ...
5
votes
1answer
806 views
Running time of CDCL compared to DPLL
What's the complexity of Conflict-Driven Clause Learning SAT solvers, compared to DPLL solvers? Was it proven that CDCL is faster in general? Are there instances of SAT that are hard for CDCL but easy ...
2
votes
1answer
122 views
Show that a language belongs to the polynomial hierarchy
I think the following exercise is to "warm up", but nevertheless it's quite difficult for me:
Let $k \in \mathbb{N}$ and let $L \in \Sigma_k$. Show that also $L^{*} \in \Sigma_k$.
The following ...
0
votes
1answer
107 views
is there an example of an algorithm that has O(1/n)? [duplicate]
Possible Duplicate:
Complexity inversely propotional to $n$
I'm curious if anyone's come up with a problem or method as n => infinity t => 0. Are there any sort of cases found in quantum ...
1
vote
1answer
606 views
Asymptotic time complexity of a two-loop program
I have two pieces of code in a function which I'm trying to calculate the asymptotic running time for:
...
4
votes
1answer
1k views
Relation between interactive proof systems (IP), NP, coNP, PSPACE
I would like to ask you some clarification on the following question:
know that ${\sf NP}$ is a subset of ${\sf IP}$
and also ${\sf coNP}$ it is a subset of ${\sf IP}$.
So ${\sf IP}$ is a biggest ...
3
votes
1answer
770 views
Proving that NPSPACE $\subseteq$ EXPTIME
I am following "Introduction to the theory of computation" by Sipser.
My question is about relationship of different classes which is present in Chapter 8.2. The Class PSPACE.
$P \subseteq NP \...
3
votes
1answer
3k views
Iterative binary search analysis
I'm a little bit confused about the analysis of binary search.
In almost every paper, the writer assumes that the array size $n$ is always $2^k$.
Well I truly understand that the time complexity ...
4
votes
0answers
719 views
What is the complexity of Hoffman and Pavley's Nth best path algorithm?
I am currently working on a project where I'm using an implementation of Hoffman and Pavley's "Method for the Solution of the Nth Best Path Problem" to find n-th best path through a directed graph. ...
2
votes
1answer
2k views
Base of logarithm in runtime of Prim's and Kruskal's algorithms
For Prim's and Kruskal's Algorithm there are many implementations which will give different running times. However suppose our implementation of Prim's algorithm has runtime $O(|E| + |V|\cdot \log(|V|)...
5
votes
1answer
3k views
Multitape Turing machines against single tape Turing machines
Introduction: I recently learned that a multi-tape Turing Machine $\text{TM}_k$ is no more "powerful" than a single tape Turing machine $\text{TM}$. The proof that $\text{TM}_k \equiv \text{TM}$ is ...
2
votes
2answers
176 views
2
votes
0answers
151 views
What is the time complexity of computing $\frac{1}{2^n} {{n}\choose{(n+2)/2}}$
What is the time complexity of computing $\frac{1}{2^n} {{n}\choose{(n+2)/2}}$?
$$\frac{1}{2^n} {{n}\choose{(n+2)/2}} = \frac{1}{2^n} \frac{n(n-1)\cdots ((n-2)/2)}{((n+2)/2) (n/2) \cdots 1}$$
The ...
2
votes
1answer
970 views
Finding big O notation of function with two parameters
I'm looking to work out the big-O notation for the following:
$$\frac{n^{s + 1} - 1}{n - 1} - 1$$
I have a feeling the result is $O\left( n^s \right)$ but I'm not sure how to prove it.
Any help ...
6
votes
3answers
5k views
What is the relationship between NP/NP-Complete/NP-Hard to time complexity?
I'm familiar with a few problems of each class and even though the definitions are based on sets and polynomial reducibility, I see a pattern with time complexity. NP problems appear to be $O(2^n)$ (...
3
votes
1answer
1k views
Clarifications on polynomial reducibility for problems in P and NP-complete
Can I always increase the complexity of a problem via polynomial reduction? (in which case 'reduction' is really a misnomer) For example, if I have a classic P problem (say, finding the smallest ...
2
votes
1answer
128 views
What constitutes one operation/cycle/move in the RAM model?
I saw a RAM model diagram that displayed an input tape, output tape, the program (read-only), the instruction pointer, and the memory registers. However, when I look at questions of time complexity, ...
5
votes
3answers
304 views
Complexity inversely propotional to $n$
Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?
3
votes
3answers
1k views
How to write a recursive function that with certain time complexity
I'm now doing exam revision, and from some past year exam papers, I noticed some questions that ask to write a recursive method with signature like
...
3
votes
1answer
188 views
Complexity calculations, assumptions on basic costs [duplicate]
Possible Duplicate:
How can we assume comparison, addition, … between numbers is $O(1)$
When we calculate the time-complexity of some algorithm we make many simplifications (or assumptions)...
13
votes
2answers
18k views
12
votes
3answers
392 views
Why larger input sizes imply harder instances?
Below, assume we're working with an infinite-tape Turing machine.
When explaining the notion of time complexity to someone, and why it is measured relative to the input size of an instance, I ...
7
votes
2answers
149 views
Connection between castability and convexity
I am wondering if there are any connection between convex polygon and castable object? What can we say about castability of the object if we know that the object is convex polygon and vice versa.
Let'...
2
votes
1answer
92 views
Run time of product of polynomially bounded numbers
Let $M$ denote a set of $n$ positive integers, each less than $n^c$.
What is the runtime of computing $\prod_{m \in M} m$ with a deterministic Turing machine?
1
vote
1answer
149 views
Problem with the definition of P
In "Introduction to Algorithms: 3rd Edition" there is Theorem 34.2, which states
$P = \{ L \mid L \text{ is accepted by a polynomial-time algorithm} \}$
"Accepted in polynomial-time" is defined by:...
5
votes
3answers
251 views
Why does NTIME consider the length of the longest computation?
In Sipser's textbook "Introduction to the Theory of Computation, Second Edition," he defines nondeterministic time complexity as follows:
Let $N$ be a nondeterministic Turing machine that is a ...
3
votes
1answer
101 views
distinction between $\textbf{P}^{\# \textbf{P}}$ and $\# \textbf{P}$-Complete
We know that $\# \textbf{P}$ is closed under polynomial sums, i.e., sum of polynomially many $\# \textbf{P}$ functions is still in $\# \textbf{P}$.
Functions in $\textbf{P}^{\# \textbf{P}}$ are those ...
9
votes
1answer
266 views
Can joins be parallelized?
Suppose we want to join two relations on a predicate. Is this in NC?
I realize that a proof of it not being in NC would amount to a proof that $P\not=NC$, so I'd accept evidence of it being an open ...
4
votes
1answer
479 views
Using hash tables instead of lists for buckets in hash tables
Say instead of using a linked list as buckets for a hash table of size $m$, we use another hash table of size $p$ as buckets this time. What would be the average case for this problem?
I looked up ...
21
votes
2answers
628 views
Finding at least two paths of same length in a directed graph
Suppose we have a directed graph $G=(V,E)$ and two nodes $A$ and $B$.
I would like to know if there are already algorithms for calculating the following decision problem:
Are there at least two ...
5
votes
2answers
198 views
Semi-decidable problems with linear bound
Take a semi-decidable problem and an algorithm that finds the positive answer in finite time. The run-time of the algorithm, restricted to inputs with a positive answer, cannot be bounded by a ...
4
votes
2answers
247 views
Attempt to write a function with cubed log runtime complexity $O(\log^3 n)$
I'm learning Data Structures and Algorithms now, I have a practical question that asked to write a function with O(log3n), which means log(n)*log(n)*log(n).
...
7
votes
2answers
628 views
How many strings are close to a given set of strings?
This question has been prompted by Efficient data structures for building a fast spell checker.
Given two strings $u,v$, we say they are $k$-close if their DamerauāLevenshtein distanceĀ¹ is small, i.e. ...
11
votes
2answers
3k views
Hashing using search trees instead of lists
I am struggling with hashing and binary search tree material.
And I read that instead of using lists for storing entries with the same hash values, it is also possible to use binary search trees. And ...
13
votes
1answer
465 views
Restricted version of the Clique problem?
Consider the following version of the Clique problem where the input is of size $n$ and we're asked to find a clique of size $k$. The restriction is that the decision procedure cannot change the input ...
1
vote
3answers
2k views
Subset-sum and 3SAT
Two things (this may be naive):
Does anyone believe there is a sub-exponential time algorithm for the Subset-sum problem? It seems obvious to me that you would have to look through all possible ...
5
votes
1answer
487 views
What is the complexity of these tree-based algorithms?
Suppose we have a balanced binary tree, which represents a recursive partitioning of a set of $N$ points into nested subsets. Each node of the tree represents a subset, with the following properties: ...
9
votes
1answer
186 views
Influence of the dimension of cellular automata on complexity classes
Let's take as an example the 3d ā 2d reduction: What's the cost of simulating a 3d cellular automaton by a 2d cellular automaton?
Here is a bunch of more specific questions:
What kind of algorithms ...
18
votes
3answers
2k views
Clever memory management with constant time operations?
Let's consider a memory segment (whose size can grow or shrink, like a file, when needed) on which you can perform two basic memory allocation operations involving fixed size blocks:
allocation of ...
