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

268 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
551 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)$ ...
541 views

635 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 ...
47 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 ...
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 ...
96 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 ...
47 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$. ...
66 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 ...
679 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. ...
292 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 ...
106 views

### Polynomial-time linear-reduction from Directed Hamiltonian Path Problem to 3SAT

Is there a polynomial-time reduction from Directed Hamiltonian Path Problem to 3SAT which is linear in the number of vertices? That is, it reduces every directed graph $G$ with $n$ vertices to a ...
22 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 ...
22 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 ...
48 views

### Complexity of “Fast Poisson Disk Sampling in Arbitrary Dimensions”

I came across the paper Fast Poisson Disk Sampling in Arbitrary Dimensions which gives an algorithm for generating Poisson disk points in $\mathbb{R}^n$. It's claimed that the algorithm is linear ...
36 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 ...
80 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 ...
147 views

### “Fuzzy” Chinese Remainder Theorem

I have some "fuzzy" congruences like these: \begin{align} \\ x&\equiv a_1 \mod 3 \text{ with } a_1 \in \{0,1\},\\ x&\equiv a_2\mod 5 \text{ with } a_2 \in \{2,3,4\},\\x&\equiv a_3 \mod 7 \...
105 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. ...
145 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 ...
187 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 ...
50 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 ...
985 views

19 views

### Poset data structure to find least element, greater or equal to given

Let $A$ be a finite set, and $S \subset \mathcal{P}(A)$. Is there a data structure for $S$ that would allow to quickly retrieve an element $q \in S$, given a key $p \in \mathcal{P}(A)$, such that $q$ ...
65 views

### Consider vectorization and for loop, do both approaches have the same time complexity?

I am learning this post Fast computation of nearest neighbors is an active area of research in machine learning. The most naive neighbor search implementation involves the brute-force computation ...
38 views

### Asymtotic bound for recurrence of $T(n)=2T(n/2)+ \sum_{i=0}^{n} (i+2)^2$ using substitution

What can be an initial guess for finding the tight asymptotic bounds of $T(n)=2T(n/2)+ \sum_{i=0}^{n} (i+2)^2$ using substitution method?
42 views

38 views

### What is the time complexity of FC_MRV algorithm?

I am studying CSP and read the papers on it.I wanted to know the time complexity of Forward checking with Minium Remaining Value algorithm.
44 views

### Computational complexity of Wang tiling of a finite plane

For a given set of Wang tiles on an $L \times L$ plane (where a tile is $1\times 1$) we first need to determine whether a tiling of the plane is possible. If so, we can then consider the problem of ...