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.

Filter by
Sorted by
Tagged with
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

Time complexity of a triple-nested loop

Please consider the following triple-nested loop: ...
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 ...

1
34 35 36 37
38