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,621
questions
86
votes
6
answers
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 ...
user742
73
votes
4
answers
118k
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 ...
- 851
65
votes
8
answers
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
64
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,451
60
votes
3
answers
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
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.7k
31
votes
2
answers
31k
views
Why is push_back in C++ vectors constant amortized?
I am learning C++ and noticed that the running time for the push_back function for vectors is constant "amortized." The documentation further notes that "If a reallocation happens, the reallocation is ...
- 1,607
31
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 ...
- 452
31
votes
0
answers
813
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)$ ...
- 441
29
votes
4
answers
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
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 ...
- 9,086
27
votes
4
answers
7k
views
Which Grows Faster: Factorial or Double Exponentiation
Which of the functions among $2^{3^n}$ or $n!$ grows faster?
I know that $n^n$ grows faster than $n!$ and $n!$ grows faster than $c^n$ where $c$ is a constant, but what is it in my case?
- 1,200
27
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 ...
- 968
27
votes
3
answers
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
27
votes
2
answers
9k
views
Is there a name for the class of algorithms that are the most efficient for a particular task?
This would be analogous to the Kolmogorov complexity of a string, except that in this case, I'm interested in the algorithm that solves a given problem using the least number of steps.
We would ...
- 373
27
votes
2
answers
5k
views
Understanding of big-O massively improved when I began thinking of orders as sets. How to apply the same approach to big-Theta?
Today I revisited the topic of runtime complexity orders – big-O and big-$\Theta$. I finally fully understood what the formal definition of big-O meant but more importantly I realised that big-O ...
- 401
23
votes
2
answers
4k
views
How is the traveling salesman problem verifiable in polynomial time?
So I understand the idea that the decision problem is defined as
Is there a path P such that the cost is lower than C?
and you can easily check this is true by verifying a path you receive.
...
- 559
23
votes
1
answer
742
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 \...
- 2,299
22
votes
3
answers
2k
views
Do functions with slower growth than inverse Ackermann appear in runtime bounds?
Some complicated algorithms (union-find) have the nearly-constant inverse Ackermann function that appears in the asymptotic time complexity, and are worst-case time optimal if the nearly constant ...
- 1,721
22
votes
2
answers
723
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
21
votes
7
answers
6k
views
in O(n) time: Find greatest element in set where comparison is not transitive
Title states the question.
We have as inputs a list of elements, that we can compare (determine which is greatest). No element can be equal.
Key points:
Comparison is not transitive (think rock ...
- 319
21
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 ...
- 693
21
votes
2
answers
886
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 ...
- 351
20
votes
7
answers
19k
views
What are the characteristics of a $\Theta(n \log n)$ time complexity algorithm?
Sometimes it's easy to identify the time complexity of an algorithm my examining it carefully. Algorithms with two nested loops of $N$ are obviously $N^2$. Algorithms that explore all the possible ...
- 755
20
votes
3
answers
19k
views
Why are loops faster than recursion?
In practice I understand that any recursion can be written as a loop (and vice versa(?)) and if we measure with actual computers we find that loops are faster than recursion for the same problem. But ...
- 1,006
20
votes
3
answers
12k
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 ...
- 882
20
votes
1
answer
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
20
votes
2
answers
8k
views
Difference between time complexity and computational complexity
For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them?
I used to calculate the maximum (worst) count of basic (most ...
- 413
20
votes
1
answer
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 ...
- 1,489
20
votes
2
answers
4k
views
How to find the element of the Digit Sum sequence efficiently?
Just out of interest I tried to solve a problem from "Recent" category of Project Euler ( Digit Sum sequence ). But I am unable to think of a way to solve the problem efficiently. The problem is as ...
- 2,972
20
votes
1
answer
976
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 ...
user742
20
votes
1
answer
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)$ ...
- 968
19
votes
5
answers
8k
views
Time complexity of an algorithm: Is it important to state the base of the logarithm?
Since there is only a constant between bases of logarithms, isn't it just alright to write $f(n) = \Omega(\log{n})$, as opposed to $\Omega(\log_2{n})$, or whatever the base might be?
- 371
19
votes
3
answers
7k
views
Time complexity $O(m+n)$ Vs $O(n)$
Consider this algorithm iterating over $2$ arrays $(A$ and $B)$
size of $ A = n$
size of $ B = m$
Please note that $m \leq n$
The algorithm is as follows
...
- 291
19
votes
7
answers
5k
views
Why do we use the number of compares to measure the time complexity when compare is quite cheap?
I think one reason a compare is regarded as quite costly is due to the historical research as remarked by Knuth, that it came from tennis match trying to find the second or third best tennis player ...
- 413
19
votes
3
answers
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 ...
- 1,490
19
votes
2
answers
682
views
Efficient algorithms for vertical visibility problem
During thinking on one problem, I realised that I need to create an efficient algorithm solving the following task:
The problem: we are given a two-dimensional square box of side $n$ whose sides are ...
- 373
18
votes
4
answers
4k
views
Is the following problem NP-hard? (or have you seen it before?)
I genuinely don't know if the following problem is NP-hard. I have never seen it mentioned online, but it's hard to even search for exact problems like this. I have been trying to find an efficient ...
- 283
18
votes
4
answers
2k
views
Measuring time complexity in the length of the input v/s in the magnitude of the input
I know that formally the time compliexity of an algorithm is measured in the length of the input, which in binary would be the number of bits required to encode the input.
The problem that I have with ...
- 183
18
votes
2
answers
17k
views
Complexity of union-find with path-compression, without rank
Wikipedia says union by rank without path compression gives an amortized time complexity of $O(\log n)$, and that both union by rank and path compression gives an amortized time complexity of $O(\...
- 710
18
votes
1
answer
4k
views
FFT-less $O(n\log n)$ algorithm for pairwise sums
Suppose we are given $n$ distinct integers $a_1, a_2, \dots, a_n$, such that $0 \le a_i \le kn$ for some constant $k \gt 0$, and for all $i$.
We are interested in finding the counts of all the ...
- 6,261
17
votes
2
answers
2k
views
Why is factoring large integers considered difficult?
I read somewhere that the most efficient algorithm found can compute the factors in $O(\exp((64/9 \cdot b)^{1/3} \cdot (\log b)^{2/3})$ time, but the code I wrote is $O(n)$ or possibly $O(n \log n)$ ...
- 173
17
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,529
17
votes
1
answer
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 ...
- 623
16
votes
5
answers
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
16
votes
1
answer
2k
views
Why aren't P and P/poly trivially the same?
The definition of P is a language that can be decided by a polynomial time algorithm. The definition of P/poly can be taken to mean a language that can be decided by a polynomial-size circuit (see ...
- 271
16
votes
2
answers
1k
views
A dense NP complete language implies P=NP
We say that the language $J \subseteq \Sigma^{*}$ is dense if there exists a polynomial $p$ such that $$ |J^c \cap \Sigma^n| \leq p(n)$$ for all $n \in \mathbb{N}.$ In other words, for any given ...
- 2,450
15
votes
4
answers
2k
views
Is there a known polynomial time complexity problem with bad constants?
As you know, big O notation hides all constants. For instance, both runtimes $T_1=n$ and $T_2=10^{10}n$ are considered to be linear ($\mathcal{O(n)}$).
Is there an iconic problem whose best known ...
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
15
votes
2
answers
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