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

211 questions
Filter by
Sorted by
Tagged with
22k 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 ...
5k 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. ...
• 20.7k
5k views

### Can one show NP-hardness by Turing reductions?

In the paper Complexity of the Frobenius Problem by Ramírez-Alfonsín, a problem was proved to be NP-complete using Turing reductions. Is that possible? How exactly? I thought this was only possible by ...
• 693
6k 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 ...
• 968
43k 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 ...
• 2,193
21k views

### Time complexity of a triple-nested loop

Please consider the following triple-nested loop: ...
• 131
19k views

### algorithm time analysis "input size" vs "input elements"

I'm still a bit confused with the terms "input length" and "input size" when used to analyze and describe the asymptomatic upper bound for an algorithm Seems that input length for the algorithm ...
• 519
732 views

### Is there an efficient algorithm for expression equivalence?

e.g. $xy+x+y=x+y(x+1)$ ? The expressions are from ordinary high-school algebra, but restricted to arithmetic addition and multiplication (e.g. $2+2=4; 2.3=6$), with no inverses, subtraction or ...
• 283
3k views

### minimum subset of dominating 2D points

From an initial set $S$ of 2D points, how to efficiently compute a minimum(-size) dominating subset $M$ ? $M$ is a dominating subset of $S$ if for any $(x,y)$ in $S$ there is at least one point (a,b) ...
• 218
203k views

### What is a the fastest sorting algorithm for an array of integers?

I have come across many sorting algorithms during my high school studies. However, I never know which is the fastest (for a random array of integers). So my questions are: Which is the fastest ...
• 991
9k views

### Is it really possible to prove lower bounds?

Given any computational problem, is the task of finding lower bounds for such computation really possible? I suppose it boils down to how a single computational step is defined and what model we use ...
• 733
6k views

### Is there a meaningful difference between O(1) and O(log n)?

A computer can only process numbers smaller than say $2^{64}$ in a single operation, so even an $O(1)$ algorithm only takes constant time if $n<2^{64}$. If I somehow had an array of $2^{1000}$ ...
1k views

### Are there strongly-polynomial algorithms that take more than polynomial time?

In [1] strongly-polynomial is defined as either: The algorithm runs in strongly polynomial time if the algorithm is a polynmomial space algorithm and performs a number of elementary arithmetic ...
• 347
1 vote
235 views

### If a language is X-complete, is its complement is X-complete as well?

I'm looking for an information about closure of complexity complete classes. Is it true that any language, if the language is X-complete, then its complement is X-complete? Why? I was thinking ...
• 339
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 ...
• 1,451
4k views

### Efficient algorithm to compute the $n$th Fibonacci number

The $n$th Fibonacci number can be computed in linear time using the following recurrence: ...
• 271
1k views

### Does the complexity of strongly NP-hard or -complete problems change when their input is unary encoded?

Does the difficulty of a strongly NP-hard or NP-complete problem (as e.g. defined here) change when its input is unary instead of binary encoded? What difference does it make if the input of a ...
• 693
11k views

### Time complexity of base conversion

Why can't arbitrary base conversion be as fast as converting from base $b$ to base $b^k$ ? Seems to be a big time complexity difference! I am also interested in reading material about it. Old. ...
• 703
2k views

### Time Complexity of Regular Languages

I wonder how I can go about proving that if a language L is decidable in o(nlog(n)) then L must be regular. I should probably mention that by "decidable" I mean "being decidable by single-tape ...
709 views

### Modeling the problem of finding all stable sets of an argumentation framework as SAT

As a continuation of my previous question i will try to explain my problem and how i am trying to convert my algorithm to a problem that can be expressed in a CNF form. Problem: Find all stable sets ...
• 415
235 views

### Find two numbers in array $A$ such that $|x-y| \leq \frac{\max(A)-\min(A)}n$ in linear time

I'm struggling with the following question: Let $\langle a_0, a_1,\dots,a_n\rangle$ be a sequence of real numbers, and let $M = \max\{a_0, a_1, .... a_n\}$ and $m = \min\{a_0, a_1, .... a_n\}$....
• 203
810 views

### Confusion about the Time Hierarchy Theorem and relativization

I know that $\mathsf{P}^A = \mathsf{EXP}$ for any $\mathsf{EXPTIME}$-complete language $A$. Is it true that $\mathsf{DTIME}^A(n^k) = \mathsf{EXP}$ for any fixed $k$ and any $\mathsf{EXPTIME}$-...
• 1,621
1 vote
281 views

### sort array with some of the elements in a known range

Let $A$ be an array of n elements. We know that $n - \lfloor \sqrt n \rfloor$ elements are integers in range $\sqrt n$ to $n\sqrt n$ (the other $\lfloor \sqrt n \rfloor$ elements may or may not be in ...
• 261
119k views

### What exactly is polynomial time?

I'm trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn't find an exact definition anywhere. I assume it is the complexity that is not exponential....
• 703
3k views

### Problems that are polynomially "hard" to compute but "easy" to verify

In the (unlikely) event that $P=NP$ with a constructive proof of a polynomial time algorithm that solves 3SAT, obviously things will be very different. However, practically, it could happen that the ...
• 452
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 ...
• 9,076
722 views

### Problems that provably require quadratic time

I'm looking for examples of problem which has a lower bound of $\Omega(|x|^2$) for input $x$. The problem needs to have the following properties: $\Omega(n^2)$ runtime proof for any algorithm - ...
• 2,634
15k views

### Can a Big-Oh time complexity contain more than one variable?

Let us say for instance I am doing string processing that requires some analysis of two strings. I have no given information about what their lengths might end up being, so they come from two distinct ...
• 423
5k views

### Why not to take the unary representation of numbers in numeric algorithms?

A pseudo-polynomial time algorithm is an algorithm that has polynomial running time on input value (magnitude) but exponential running time on input size(number of bits). For example testing whether ...
• 1,529
4k views

### What is the most efficient algorithm to compute polynomial coefficients from its roots?

Given $n$ roots, $x_1, x_2, \dotsc, x_n$, the corresponding monic polynomial is $$y = (x-x_1)(x-x_2)\dotsm(x-x_n) = \prod_{i}^n (x - x_i)$$ To get the coefficients, i.e., $y = \sum_{i}^n a_i x^i$, a ...
• 253
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 ...
• 231
1k views

### Machines in P undecidable?

Given a Turing machine $M$, we say that $L(M) \in P$ if the language decided by the machine can be decided by some machine in polynomial time. We say that $M \in P$ if the machine runs in polynomial ...
• 125
4k views

### Why is not known whether integer factorization can be done in polynomial time knowing how to do primality tests efficiently?

First of all, I have just started studying computer science by myself and maybe I just need some clarification of what "polynomial time" means regarding the time complexity of an algorithm and ...
• 191
2k views

### Quantum computers, parallel computing and exponential time

I've read that quantum computers can solve 'certain problems' exponentially better than classical computers. As I think I understand it, it's NOT the same to say that quantum computers take any ...
• 703
734 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. ...
• 72.4k
390 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 ...
• 9,112
628 views

### Shouldn't complexity theory consider the time taken for different operations?

I have read the answer found here which considers the size of integers when doing comparisons and how that affects on the basic cost of comparison. I am trying to understand why each basic operation ...
4k views

### Multitape Turing machines against single tape Turing machines

Introduction: I recently learned that a multi-tape Turing Machine $\text{TM}_k$ is no more "powerful" than a single tape Turing machine $\text{TM}$. The proof that $\text{TM}_k \equiv \text{TM}$ is ...
• 755
847 views

### Why isn't an edge-map graph implementation used in practice?

Wikipedia states that three different graph implementations are used in practice: Adjacency Lists Adjacency Matrix Incidence Matrix While I was learning about these structures, another option ...
• 151
316 views

### Complexity inversely propotional to $n$

Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?
• 153
268 views

### Why Djikstra's algorithm is said to have $\mathcal{O}(|V|^2)$ complexity?

Djikstra's algorithm assigns some number to non-removed vertex each time it finds a path from removed vertex to it. Number of assignments is $\mathcal{O}(|V|^2)$. However, complexity of assignment is ...
• 1,632
985 views

• 267
562 views

### Generalized Geography with repetitions

Consider the "Generalized Geography" game: on directed graph G with selected start node, players take turns moving along edges, without ever going back to previously visited nodes. Last player to ...
1 vote
2k views

### An $O(n^2)$ is faster than an $O(n\log n)$ algorithm for small $n$

If $n<100$ then $O(n^2)$ is more efficient, but if $n\ge 100$ then $O(n\log n)$ is more efficient. I am sure that this statement is valid, but I don't know how to prove it or justify it. Can ...
1 vote
595 views

### Euclid's Algorithm Time Complexity

I have a question about the Euclid's Algorithm for finding greatest common divisors. gcd(p,q) where p > q and q is a n-bit integer. I'm trying to follow a time complexity analysis on the algorithm (...
• 211
1 vote
244 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 ...
1 vote
I'm trying to determine the exact complexity of finding an $n\times n$ matrix inverse of $A$. If it is known that the complexity of Gaussian elimination is $\frac{2}{3}n^3 + \frac{1}{2}n^2+O(n)$, then ...