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.

397 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
27
votes
0answers
669 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
615 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
312 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
227 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
1k 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.....
7
votes
0answers
164 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
300 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
120 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
604 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
90 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
107 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
861 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
729 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
65 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
62 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
50 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
122 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
543 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
105 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
49 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
70 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
758 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
59 views

Is every computable function the time complexity of some function?

Considering the recent question "Is there an algorithm whose time complexity is between polynomial time and exponential time?", some commenters observed that merely providing a function with ...
3
votes
0answers
101 views

Generalizing Matrix Chain problem: optimal summation in a tree

Matrix Chain Problem can be viewed as the problem of finding the optimal summation order in a path-structured tensor network. How hard is the problem if we extend it to trees? For instance, take the ...
3
votes
1answer
85 views

How is the time complexity of a non-deterministic Turing machine defined?

I read different things online about this: In Sipser, p. 283. The time-complexity of a NTM is defined as the maximum number of steps it uses on any branch on any input of length n. So this is only ...
3
votes
0answers
36 views

Computational Complexity of 3SAT variant with additional restrictions on variables/clauses

Given a 3SAT problem with the additional constraints that: No clause or set of clauses is the 3SAT instance is 'redundant'. Thus, this 3SAT cannot eliminate any clauses. For any/every clause, the ...
3
votes
0answers
55 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
53 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
61 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 ...
3
votes
0answers
19 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
42 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
25 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
28 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
73 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
88 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
260 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
60 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
112 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
562 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
292 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
49 views

Bowyer-Watson Delaunay Triangulation neighbour walk in $O(n^{1/d})$

The Bowyer-Watson Algorithm for creating Delaunay Triangulations works iteratively. Let's say that we have a Delaunay triangulation of $n-1$ points. Now we add the $n$-th point. In order to update the ...
2
votes
1answer
31 views

Range queries with O(N log N) build and O(1) query

I read somewhere that you can compute range queries in O(1) with O(N log N) preprocessing for any associative operation (but not necessarily invertible or idempotent). How do you do this? I know this ...
2
votes
0answers
17 views

UCYCLE in LOGSPACE and linear time

Consider UCYCLE, the problem of recognizing undirected graphs containing a cycle. On the one hand, it's in LOGSPACE, see this stackexchange thread: start at every vertex $v$ a DFS and check whether it ...
2
votes
0answers
25 views

Fast calculations using fast-Fourier convolution

Consider an array $X$ with shape $H \times W$. Let $Y$ be the other array of the same shape and $Z$ is an array of shape $h \times w$. We want to construct an array $R$ of shape $(H-h + 1, W-w+ 1)$ by ...
2
votes
0answers
40 views

How is red-black tree insertion more effective than avl tree insertion

I'm having trouble understanding why RB tree insertion is called more effective in all sources. It's said that AVL trees require "more rotations" than RB trees, but from what I've learned I ...
2
votes
0answers
35 views

Kolmogorov complexity of probability distributions, with and without time bound

Kolmogorov complexity of a string is the length of the shortest algorithm that generates it. Here I'm focusing instead on randomly distributed strings $x$, with length $n$, with a probability ...
2
votes
0answers
92 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
0answers
71 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 ...

1
2 3 4 5
8