# 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.

2,156 questions
Filter by
Sorted by
Tagged with
14 views

### Do time-constructible functions exist in relativized worlds?

I know that time-constructible functions are necessary to prove the Time Hierarchy Theorem and being computable functions they are computed by Turing Machines. I'm just confused in that since the Time ...
84 views

### Is $P=NP$ even if we need infinitely many algorithms?

If $P=NP$ was proven with an algorithm, would that have to mean that there is one algorithm that has to work for all inputs of length $n$? More specifically, what if there were infinitely many ...
41 views

### Does $P=NP$ require an algorithm that uses polynomial space?

if there was an algorithm that runs in polynomial time, but its size requires $O(2^n)$ bits, would that still prove $P=NP$?
28 views

### What is the complexity of (prime?) factorization with a fixed number of primes?

I was wondering what the complexity of factorization (on quantum computers or classical computers) is if we know that there must be exactly two prime numbers and we know the two prime numbers. For ...
21 views

### Query regarding Length of an Input and Time Complexity of algorithms

What is actually meant when we say 'size/length of an input'? As far as I have interpreted it in different books,it means the values of the parameters to be inputted in an algorithm. But I am actually ...
29 views

### Is ${\Sigma_2^\textsf{P}}^\textsf{coNP}\subseteq\textsf{PH}$?

I'd like to know if ${\Sigma_2^\textsf{P}}^\textsf{coNP}\subseteq\textsf{PH}$ or not. I know ${\Sigma_2^\textsf{P}}^\textsf{NP}=\Sigma_3^\textsf{P}\subseteq\textsf{PH}$, and I wish to know if this ...
23 views

### Complexity of checking graph separation

Let $G=(V,E)$ be an undirected graph and $A,B,C\subset V$ disjoint subsets of $V$. I want to check whether or not $A$ and $B$ are separated by $C$ (i.e. every path from $A$ to $B$ passes through $C$). ...
43 views

### Having a set of non unique Key-Value pairs, how can I optimally find a lowest sum subset if distinct keys?

I understand that the title might be confusing so I'll lead with an example. I have the following set (actually a map): ...
125 views

### Topological sort and finding longest path in DAG to solve a stacking boxes variation (no rotation)

Given n elements (boxes) I have to output the max number of boxes that can fit one into another. Each box has width (x), height (y) and depth (z). One box j can hold another box k if: ...
60 views

### O(m) time algorithm to check for a strongly connected graph

Given a directed graph G=(V,E) how can I check to see if it is strongly connected i.e. every vertex is reachable from every other vertex. what's a good algorithm to check for this that runs in O(m) ...
60 views

### Complexity analysis for finding all powers of 2 within a range

Suppose you're given $x,y$ integers s.t. $x \leq y$. I want to find all values $\in [x, y]$ (inclusive) that are a power of $2$. There's a $O(\log y)$ approach, where you just start at $1$, and ...
32 views

### How does Bowyer-Watson algorithm for Delaunay triangulation run in $O(n^2)$ but runs over all the simplexes?

The Bowyer-Watson algorithm for Delaunay triangulation is known to run in $O(n^2)$ according to the authors, where $n$ is the number of data points in $\mathbb R^d$. In addition, the algorithm (for ...
35 views

### Sequence of points on a line whose intervals represent a set of contiguous integers

If I have points on a line at positions (0), (1), (3), and (7) the set of intervals between any two points is the set of integers (1,2,3,4,6,7). In-general, a set of N unique integers can be ...
89 views

### Why there is $\log n$ factor in time constructible definition?

I saw two different definitions of time constructible functions. In Sipser (third edt), Definition 9.8, defines $t(n)$ is time constructible if $t(n)\geq O(n \log n)$ and maps $1^n$ to the binary ...
122 views

### Time Complexity for brute force algorithm finding cliques of size k in a graph, in terms of n m and k

I currently have an algorithm that uses brute force/exhaustive search to find all of the cliques of size exactly k in a graph G. My algorithm is as follows: Generate all subgraphs of size k, and check ...
18 views

24 views

### Given a list of comparisons, sort items with as few additional comparisons as possible

You have n items x, ..., x[n-1]. Beforehand, you're given a list of several comparisons ...
28 views

### Sorting from independently chosen comparisons

I want to sort a list of n items from pairwise comparisons. Each round, I receive k comparisons, one each from ...
19 views

### Time Complexity of given functions [duplicate]

What is if we have f(n) = 15n^2logn +500n^2,5 , g(n) = n^3 + 1000 , h(n) = 21n^3logn , x(n) = 50n^2,5 + n*log(n) How to check " is ...
43 views

### Ask for help to prove a inequality, thanks

Can anyone help to prove that $\sum\limits_{i=0}^{k-2}\log_2\left(\frac{n-i}{k-i-1}\right) > cn$ for some constant $c>0$? Here $k=\Big[\frac{n}{2\log_2 n}\Big]$ and $[x]$ denotes the integer ...
54 views

### Writing efficient code [closed]

I am new to programming and trying to get better at writing efficient code. The obvious thing to do is practice and gain experience. I did learn a few general pointers through exercising, but in most ...
71 views

### Can this recursive algorithm be converted to an iterative algorithm in O(1) space?

I am trying to convert this recursive algorithm ...
139 views

### Spanning tree whose sum of edge weights are between two boundries

I saw this problem: $\langle G,w,k_1,k_2 \rangle \in L$ iff Graph $G$ has a spanning tree whose sum of edge wights are less than $k_2$ and greater than $k_1$. The problem says that we can prove this ...
22 views

### NP problem: certificate concept clarification

When proving a problem in NP, e.g. k-clique problem defined as k-clique:= {<G,k>| G has a clique of size at least k }, from what I understand is that all we assume for the certificate "c&...
39 views

### Best algorithm for Decisional 4-XOR problem?

Decisional 4-XOR Problem: Assume $M>>n$ (e.g. $M=50n$ ). Let $A_1,A_2,A_3,A_4$ be sets consisting of $M$-bit elements. Each set has order exactly $2^n$. Decide whether or not there exists \$a_i \...
52 views

### Why 2^(2n+2) not equal to θ(2^2n)?

I'm trying to prove this expression 2^(2n+2) ≠ θ(2^2n)? Firstly 0 <= c1.2^(2n) <= 2^(2n+2) for this n=1 c1=1 is a solution set. For n = ∞, 0 <= ∞.c1 <= ∞ c1=1 is provide it. So omega ...