# 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,195 questions
Filter by
Sorted by
Tagged with
354 views

### What is the complexity of this subset merge algorithm?

Updated Algorithm: There was a major flaw in my original presentation of the algorithm which could have impacted the results. I apologize for the same. The correction has been posted underneath. The ...
412 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 ...
95 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?
921 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 ...
154 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:...
4k views

### How fast can we find all Four-Square combinations that sum to N?

A question was asked at Stack Overflow here: Given an integer $N$, print out all possible combinations of integer values of $A,B,C$ and $D$ which solve the equation $A^2+B^2+C^2+D^2 = N$. This ...
288 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 ...
108 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 ...
9k views

### Most efficient known priority queue for inserts

In terms of asymptotic space and time complexity, what is the most efficient priority-queue? Specifically I am looking for priority queues which minimize the complexity of inserts, it's ok if deletes ...
1k views

### Lock-free, constant update-time concurrent tree data-structures?

I've been reading a bit of the literature lately, and have found some rather interesting data-structures. I have researched various different methods of getting update times down to $\mathcal{O}(1)$ ...
11k views

### How hard is finding the discrete logarithm?

The discrete logarithm is the same as finding $b$ in $a^b=c \bmod N$, given $a$, $c$, and $N$. I wonder what complexity groups (e.g. for classical and quantum computers) this is in, and what ...
534 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 ...
1k views

### What is the average search complexity of perfect hashing?

The lookup time in perfect hash-tables is $O(1)$ in the worst case. Does that simply mean that the average should be $\leq O(1)$?
3k views

### What's the complexity of Spearman's rank correlation coefficient computation?

I've been studying the Spearman's rank correlation coefficient $\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2 \sum_i(y_i-\bar{y})^2}}$. for two ...
728 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 ...
3k views

### What is the time complexity of this function?

This is an example in my lecture notes. Is this function with time complexity $O(n \log n)$?. Because the worst case is the funtion goes into else branch, and 2 ...
516 views

### Time-space tradeoff for missing element problem

Here is a well-known problem. Given an array $A[1\dots n]$ of positive integers, output the smallest positive integer not in the array. The problem can be solved in $O(n)$ space and time: read the ...
206 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 ...
3k views

### Brute force Delaunay triangulation algorithm complexity

In the book "Computational Geometry: Algorithms and Applications" by Mark de Berg et al., there is a very simple brute force algorithm for computing Delaunay triangulations. The algorithm ...
276 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). ...
984 views

### Has anyone found polynomial algorithm on Hamiltonian cycle isomorphism?

As the title says, has anyone found a polynomial time algorithm for checking whether two graphs having a Hamiltonian cycle are isomorphic? Is this problem NP-complete?
273 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 ...
112 views

### Complexity class that properly included in DLOGTIME

Is there any decision problem that is in a complexity class properly included in DLOGTIME? (except $O(1)$, of course) If there is, can we create complete problems for DLOGTIME? So, can there be ...
5k views

### Data structure with search, insert and delete in amortised time $O(1)$?

Is there a data structure to maintain an ordered list that supports the following operations in $O(1)$ amortized time? GetElement(k): Return the $k$th element of the list. InsertAfter(x,y): Insert ...
95k views

### Find median of unsorted array in $O(n)$ time

To find the median of an unsorted array, we can make a min-heap in $O(n\log n)$ time for $n$ elements, and then we can extract one by one $n/2$ elements to get the median. But this approach would take ...
662 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. ...
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 ...
150 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'...
20k views

### How can we assume that basic operations on numbers take constant time?

Normally in algorithms we do not care about comparison, addition, or subtraction of numbers -- we assume they run in time $O(1)$. For example, we assume this when we say that comparison-based sorting ...
486 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 ...
7k views

### Complexity of finding the largest $m$ numbers in an array of size $n$

What follows is my algorithm for doing this in what I believe to be $O(n)$ time, and my proof for that. My professor disagrees that it runs in $O(n)$ and instead thinks that it runs in $\Omega(n^2)$ ...
8k views

### Complexity of computing matrix powers

I am interested in calculating the $n$'th power of a $n\times n$ matrix $A$. Suppose we have an algorithm for matrix multiplication which runs in $\mathcal{O}(M(n))$ time. Then, one can easily ...
727 views

### Finding a 5-Pointed Star in polynomial time

I want to establish that this is part of my homework for a course I am currently taking. I am looking for some assistance in proceeding, NOT AN ANSWER. This is the question in question: A 5-...
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 ...
960 views

### Optimal algorithm for finding the girth of a sparse graph?

I wonder how to find the girth of a sparse undirected graph. By sparse I mean $|E|=O(|V|)$. By optimum I mean the lowest time complexity. I thought about some modification on Tarjan's algorithm for ...
8k views

### Complexity of Towers of Hanoi

I ran into the following doubts on the complexity of Towers of Hanoi, on which I would like your comments. Is it in NP? Attempted answer: Suppose Peggy (prover) solves the problem & submits it ...
1k views

### Is there a 'string stack' data structure that supports these string operations?

I'm looking for a data structure that stores a set of strings over a character set $\Sigma$, capable of performing the following operations. We denote $\mathcal{D}(S)$ as the data structure storing ...
5k views

### Algorithmic intuition for logarithmic complexity

I believe I have a reasonable grasp of complexities like $\mathcal{O}(1)$, $\Theta(n)$ and $\Theta(n^2)$. In terms of a list, $\mathcal{O}(1)$ is a constant lookup, so it's just getting the head of ...
511 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: ...
4k views

### Decision problems vs "real" problems that aren't yes-or-no

I read in many places that some problems are difficult to approximate (it is NP-hard to approximate them). But approximation is not a decision problem: the answer is a real number and not Yes or No. ...
189 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 ...
37k views

### The time complexity of finding the diameter of a graph

What is the time complexity of finding the diameter of a graph $G=(V,E)$? ${O}(|V|^2)$ ${O}(|V|^2+|V| \cdot |E|)$ ${O}(|V|^2\cdot |E|)$ ${O}(|V|\cdot |E|^2)$ The diameter of a ...
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 ...