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.
199
questions
84
votes
6
answers
21k
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 ...
user742
40
votes
3
answers
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.5k
26
votes
2
answers
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 ...
- 948
20
votes
2
answers
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 ...
- 683
28
votes
4
answers
41k
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,163
13
votes
2
answers
20k
views
15
votes
2
answers
18k
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
13
votes
2
answers
697
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
3
votes
4
answers
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
63
votes
8
answers
200k
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 ...
- 981
25
votes
3
answers
8k
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 ...
- 713
6
votes
7
answers
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}$ ...
- 161
6
votes
1
answer
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
1
answer
214
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 ...
- 329
61
votes
8
answers
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,391
15
votes
5
answers
3k
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:
...
- 261
12
votes
4
answers
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 ...
- 683
11
votes
3
answers
10k
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. ...
- 693
8
votes
1
answer
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 ...
6
votes
1
answer
762
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,601
6
votes
3
answers
212
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
6
votes
2
answers
645
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
1
vote
2
answers
233
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
55
votes
3
answers
103k
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....
- 653
30
votes
2
answers
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 ...
- 442
28
votes
1
answer
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 ...
- 8,986
21
votes
2
answers
648
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,624
19
votes
1
answer
14k
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 ...
- 413
16
votes
3
answers
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,477
15
votes
2
answers
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
11
votes
3
answers
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 ...
- 221
8
votes
2
answers
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
8
votes
4
answers
3k
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
7
votes
2
answers
697
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. ...
- 71.6k
7
votes
2
answers
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 ...
- 693
6
votes
3
answers
338
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 ...
- 8,967
6
votes
3
answers
572
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 ...
- 413
5
votes
1
answer
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 ...
- 765
5
votes
2
answers
719
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
5
votes
3
answers
312
views
Complexity inversely propotional to $n$
Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?
- 153
4
votes
1
answer
710
views
Oracle Turing Machine EXP^EXP
I'm reading Arora Barak and in that it is written that when $O \in \mathrm{P}$, then $\mathrm{P}^O = \mathrm{P}$. Can this be generalized?
Intuitively, I think that $\mathrm{NP}^\mathrm{NP} \neq \...
- 43
4
votes
2
answers
247
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,393
3
votes
1
answer
3k
views
How can I prove DP completeness?
We defined the class $\text{DP}$ like this:
$$\text{DP} := \{ A \setminus B : A, B \in \text{NP} \}$$
We say a problem $P$ is $\text{DP}$ complete iff $P \in \text{DP}$ and $X \leq P \forall X \in \...
- 257
2
votes
1
answer
440
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 ...
- 57
1
vote
3
answers
877
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 ...
- 57
1
vote
1
answer
561
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
3
answers
216
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 ...
- 358
1
vote
1
answer
3k
views
Complexity of matrix inverse via Gaussian elimination
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 ...
- 131
0
votes
1
answer
2k
views
Relationship between an integer N and the number of bits n required to represent the integer
I'm trying to understand the time complexity of the following code in terms of n.
Pseudocode for trial division:
I understand that the time complexity of the algorithm is O(sqrt(N)). However, can ...
0
votes
2
answers
98
views
Can you always prove the asymptotic bound of a recurrence of the form aT(n/b) + f(n) using the substitution method?
To make my question more concrete, here is an example I am stuck on.
I want to prove that $T(n) = 8T(\frac{n}{2}) + n^3$ is asymptotic bound by $n^3\log(n)$ using the substution method. That is $T(n)$...
- 103