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.

364 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
26
votes
0answers
650 views

Largest set of cocircular points

Given $n$ points with integer coordinates in the plane, determine the maximum number of points that lie on the same circle (on its circumference, not its interior). This can be done in $O(n^3)$ ...
20
votes
0answers
599 views

Complexity of deciding whether there is a winning strategy in the following game

The sum divider game for $n$ starts with the set $M_0 = \{1,\dots,n\}$. Player A chooses a number $m_1$ from $M_0 \setminus \{1\}$ and B has to choose a divider $m_2$ of $m_1$ from $M_1 = M_0 \...
9
votes
0answers
306 views

P vs NP and the Time Hierarchy

Assuming $P\neq NP$, is it possible that there exists a $k$ such that $P\subseteq\textsf{NTIME}(t^k)$? There reason I ask this is that I assume the following: $$P=NP \implies \forall k\ \exists j.\ \...
8
votes
0answers
215 views

Complexity of removing edges to eliminate a perfect matching

Suppose $G$ is a bipartite graph which has a perfect matching. I want to find the fewest number of edges to delete from $G$ so that a perfect matching no longer exists. What is the complexity of this ...
8
votes
0answers
990 views

Complexity of Sorting Integers on a Multitape Turing Machine

How expensive is sorting integers on a Multitape Turing Machine? Well known sorting algorithms, like quicksort, tend to rely on jumping / indirect-access being cheap. But MTMs have no indirect access.....
8
votes
2answers
892 views

Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations?

I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in ...
7
votes
0answers
162 views

Overlap Maximization problem

Here's the problem: I have a collection of collections, $C$, where each $c\in C$ is a collection of sets $X\subset U$. Denote $c_i$ as the i-th $X$ in $c$. Informally, I want to map all the sets in ...
6
votes
0answers
288 views

Prove/disprove the existance of a data structure that has O(log N) inserts/deletes and get k-th largest element in O(1)

Consider a sorted array. We can get the $k$-th largest element in $O(1)$, but insertions and deletions cost $O(n)$. Consider an order statistic tree. Insertions and deletions cost $O(\log{N})$, but ...
6
votes
0answers
119 views

Problems with Θ(n³) complexity on TMs with lower bounds by communication complexity arguments

One of the most used simple examples of application of Communication Complexity is the $\Omega(n^2)$ lower bound for recognizing palindromes of length $2n$ on a single tape Turing machine. Is there a ...
5
votes
0answers
398 views

Determinant calculation - Bareiss vs. Gauss Algorithm

I've been working on a matrix-library in C++ for a while and amongst other functions, I've implemented two functions for calculating the determinant of a matrix: Gauss-Algorithm: This algorithm is ...
5
votes
0answers
86 views

Given $n=pq=a^2+b^2$, can we factor $n$?

Just to be clear, $a$ and $b$ are known, while $p$ and $q$ are unknown prime numbers, both congruent to $1$ modulo $4$. Can we design an efficient algorithm to retrieve $p$ and $q$? It is a known ...
5
votes
0answers
103 views

Specific quadratic 0-1 knapsack problem solvable in linear time?

I am interested in a simple variant of the quadratic knapsack problem. Let $\{w_1, \ldots, w_n\} \in \{0,1\}$ be $n$ weights and $\{v_1, \ldots, v_n\} \in \mathbb{R}$ be $n$ values. Furthermore, ...
5
votes
0answers
2k views

Time Complexity of a Knapsack-derived problem

Consider the following problem: Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer. Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a ...
5
votes
0answers
742 views

Non-deterministic time hierarchy theorem: universal TM overhead

I am currently reading the book of Arora and Barak on computational complexity. In the third chapter (p69-70), two classic theorems regarding time complexity hierarchies are introduced: $\left[f(n)\...
5
votes
0answers
707 views

Time complexity of finding the largest factor of a number (using a specific oracle)

My question is related to this question posted on math.SE: Given an odd number, what is the quickest (constant-time) algorithm for finding its largest factor and suppose you can call a helper ...
4
votes
0answers
51 views

Simultaneous reachability of NFA states

Suppose I have a $n$-state non-deterministic finite automaton $F$ over alphabet $\Sigma$. Let $S(x)$ be the set of states reachable from the starting state by consuming string $x$. I am interested for ...
4
votes
0answers
60 views

Algorithm for Unique Selections

Suppose I have $k$ sets with $n$ elements in each. Define a selection as one element taken from each set. A selection is unique if there's one and only one way it can happen—that is, one and only one ...
4
votes
0answers
49 views

Highest stack of rectangles

Suppose we have a set of $n$ dimensional rectangles $R = \{(x_{i,1}, \ldots, x_{i,n}), i \in 1 \ldots k\}$. We want to create the highest stack in say the first dimension such that each side of the ...
4
votes
1answer
116 views

Survival algorithm for Network deterministic failures

Consider an undirected network $G = (V,E)$ in which edge $e$ $\in$ $E$ fails after (deterministic) time $t(e) > 0$. Network failure occurs at the first instant in which $G$ is no longer connected. ...
4
votes
0answers
450 views

Time complexity of obtaining the set of distinct elements in a sequence?

Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in O(1) time with arbitrary positions). What's known ...
4
votes
0answers
104 views

How hard is recovering an invertible binary matrix from its check sums?

This is a follow-up question on my previous one, How hard is recovering a binary matrix from its check sums?. Consider the following problem, which adds an extra restriction that the matrix be ...
4
votes
0answers
48 views

Complexity class of finding the number of walks of length $k$ that have different vertex sets

Vertex set $A$ is of the form: $A = \{(v_1,r_1),(v_2,r_2),...\}$ where $v_1 \in V$ and $r_1$ refers to the number of times $v_1$ is reached in some walk and $v_j \neq v_i$ whenever $i \neq j$. ...
4
votes
0answers
69 views

PTAS vs. exact-time sub-exponential algorithms

I have recently summarized several algorithms for the maximum disjoint set problem. This problem is NP-hard, but it has both PTAS and sub-exponential algorithms. These algorithms seem to me closely ...
4
votes
0answers
740 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. ...
3
votes
0answers
53 views

How to replace the max distance of a bounded set of points with a random point in less than $O(n^2)$?

Context Let's say I have a finite set of points of size $N$. I can represent the points in a metric space and then compute distances between them. My goal is to replace a point in the set with another ...
3
votes
0answers
50 views

Make Change in Linear Time

The question is motivated by this post on StackOverflow. Given an integer $n$ and a finite list of distinct positive integers $ds$, let $f(n, ds)$ denote the number of ways $n$ can be expressed as a ...
3
votes
0answers
18 views

Spanning hypertree which connects the vertices as slowly as possible

I want to find a reference for the following problem or a similar problem for my paper. I found a greedy algorithm for this problem, but writing such an algorithm in a paper is not common in my area, ...
3
votes
0answers
34 views

What's the best non-amortized disjoint set?

In practice, the amortized O(α(n)) data structure is good for every case. But if I want to be pedantic and require each operation to be under a certain time complexity, what's the currently known best ...
3
votes
0answers
24 views

Bit complexity of computing the sign of an expression evaluated at an algebraic number

I have a univariate polynomial $F(t)\in \mathbb{Z}[t]$ of degree $d$ and maximum bitsize of coefficients equal to $\tau$ and $G(t) \in \mathbb{Z}[t]$ of degree $d^2$ and maximum bitsize of ...
3
votes
0answers
26 views

Complexity of finding an alternating Hamiltonian (x,y)-path in edge bicolored complete graphs

Let $G$ be a simple complete graph with an edge-2-coloring. An alternating Hamilton (x,y)-path is a Hamiltonian path which starts at vertex $x$ and ends at vertex $y$ such that the colors of its ...
3
votes
0answers
68 views

Is the definition of $\textbf{BPP}$ robust for doubly exponential small (or even smaller) error?

$\textbf{BPP}$ is usually defined in terms of probabilistic polynomial-time TMs which have an error probability of at most $\frac{1}{3}$. Furthermore, using the Chernoff bound it can be proven that ...
3
votes
0answers
85 views

Polynomial time algorithms for rank 1 elliptic curves over Q

As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way to calculate a ...
3
votes
0answers
233 views

Is it possible to compute an equality hash for nodes in a *cyclic* directed graph in less than quadratic time?

Calculating hashes for nodes in an acyclic graph is well known using a Merkle tree. With some simplifying assumptions, a simple algorithm will also calculate hashes for nodes in a cyclic graph... but ...
3
votes
0answers
59 views

Computational complexity of numerically estimating the roots of a polynomial

The Wikipedia article on finding the roots of polynomials mentions all sorts of methods to do so. But it doesn't give, nor can one easily figure out by following the links, known lower and upper ...
3
votes
0answers
1k views

Analysis of Weighted Quick Union with Path Compression

I have searched the internet for an analysis of why WQUPC is amortized $O( m \alpha (n) ) $ for m operations on n nodes ( $\alpha ( n) $ is the inverse Ackerman function). I understand why it is $O ( ...
3
votes
0answers
108 views

Are there any algorithms where the recovery of a witness changes the time complexity?

In many algorithms, such as the solution to the longest-subsequence problem using dynamic programming, finding the length of an answer (or signaling the nonexistence of an answer) is easy, but ...
3
votes
2answers
519 views

Algorithm for scheduling unit time tasks with arrival times and deadlines

Suppose we have $n$ tasks to order over $n$ days. Each tasks takes 1 day to be completed. Each task has a start date when the task becomes available and a deadline when the task must be delivered. ...
3
votes
1answer
262 views

Theoretical worst case running time of finding a path through a maze?

Given a randomly generated maze of dimensions n x n, with the entrance point always being the top left corner (0,0) and the exit point always being the bottom right corner (n,n) what is the ...
2
votes
0answers
87 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 ...
2
votes
1answer
61 views

Must all NP-complete problems have an asymptotically optimal algorithm?

According to Blum's speedup theorem, there exist problems with no asymptotically optimal algorithm. Suppose that NP-complete problems had speedup. We know a problem X with asymptotically time ...
2
votes
0answers
43 views

Median of given range of elements in a binary search tree

Given a range [l, r], we are supposed to find the median of all the nodes that are present in the binary search tree and whose values are within l and r. Let me take an example. Let the BST be the ...
2
votes
0answers
96 views

How computationally hard are the battle systems of Paper Mario and Paper Mario: The Thousand Year Door?

What is the time complexity and space complexity of working out, in suitably generalised versions of the battle systems of both Paper Mario 64 and Paper Mario: The Thousand Year Door: The minimum ...
2
votes
0answers
44 views

A simple algorithm to solve the MST Sensitivity Analysis problem in linear time when the MST is a path

The problem. Given an undirected, connected, edge-weighted graph $G=(V, E_G; w)$ and a minimum spanning tree (MST) $T=(V, E_T)$ of $G$, the MST sensitivity analysis problem asks to find, for each ...
2
votes
0answers
51 views

Two dimensional recursive function in $O(\log n)$ time complexity

It is well known that a recursive sequence or $1$-d sequence can be calculated in $O( \log n)$ time given that it has the form $$a_n=\sum_{k=1}^{n} C_ka_{n-k},$$ where $C_k$ is a constant. Examples ...
2
votes
0answers
61 views

P/NP - Proof that SAT-TM is NP-complete uses certificate

To prove that SAT-TM (Turing machine emulating the satisfiability problem) is NP-Hard $$\text{SAT-TM}:=\{⟨M,p,1^k⟩ \; | \;∃c,\; |c|\leq p(k), \;\text{such that M accepts c in ≤k steps}\}$$ my ...
2
votes
0answers
24 views

Central Trinomial Coefficients best time complexity

What is the fastest known time complexity for computing central trinomial coefficients? Let $C_n=1,1,3,7,19,51,...$ (OEIS A002426) denote the coefficient of $x^n$ in $(x^2+x+1)^n$ starting at $n=0$. ...
2
votes
0answers
46 views

Complexity of find histogram bins vs convex hull

For a list of n 2d points, finding the convex hull vertex takes O(n log(n)) time. And O(n) time if it’s sorted lexicon order. Meanwhile What’s the complexity of finding the histogram bin edges of k ...
2
votes
0answers
47 views

Fastest Algorithm for finding All Pairs Shortest Paths on Sparse Non-Negative Graph

As discussed here Johnson's Algorithm can be used to solve the APSP-Problem in $O(V^2\log V + VE)$ in stead of $O(V^3)$ for Floyd-Warshall. However, Johnsons Algorithm does quite a bit of work for the ...
2
votes
0answers
33 views

Are there problems that are known to be in ZPP but not in p

Are there any problems that are known to be in ZPP but not in p?
2
votes
0answers
89 views

What is the time complexity of the Edmonds-Karp algorithm for finding a maximum cardinality matching in bipartite graphs?

What is the time complexity of the Edmonds-Karp algorithm (not the Hopcroft-Karp algorithm) for finding a maximum cardinality matching in bipartite graphs? Is it still $O(|V||E|^2)$, or it has a ...

1
2 3 4 5
8