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.

Filter by
Sorted by
Tagged with
75
votes
6answers
17k 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 ...
60
votes
8answers
4k 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 ...
55
votes
8answers
173k 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 ...
49
votes
4answers
74k 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 ...
36
votes
3answers
3k 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. ...
36
votes
3answers
50k views

What exactly is polynomial time? [duplicate]

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....
28
votes
1answer
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 ...
27
votes
4answers
30k 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 ...
27
votes
2answers
8k 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 ...
26
votes
4answers
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?
26
votes
2answers
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 ...
25
votes
2answers
4k 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 ...
24
votes
2answers
23k 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 ...
24
votes
3answers
6k 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 ...
24
votes
0answers
559 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)$ ...
21
votes
6answers
5k 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 ...
21
votes
2answers
3k 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. ...
21
votes
3answers
1k 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 ...
20
votes
3answers
8k 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 ...
20
votes
2answers
582 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 ...
20
votes
1answer
7k 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 ...
20
votes
2answers
3k 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 ...
20
votes
1answer
921 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 ...
20
votes
1answer
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)$ ...
19
votes
4answers
5k 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?
19
votes
7answers
11k 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 ...
19
votes
2answers
3k 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 ...
19
votes
2answers
398 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 - ...
19
votes
2answers
538 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 ...
19
votes
0answers
542 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 \...
18
votes
7answers
3k 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 ...
18
votes
3answers
12k 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 ...
18
votes
3answers
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 ...
17
votes
2answers
1k 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)$ ...
16
votes
2answers
837 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 ...
16
votes
2answers
6k 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 ...
16
votes
1answer
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 uses the ...
15
votes
3answers
3k 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 ...
15
votes
2answers
436 views

Where is the mistake in this apparently-O(n lg n) multiplication algorithm?

A recent puzzle blog post about finding three evenly spaced ones lead me to a stackoverflow question with a top answer that claims to do it in O(n lg n) time. The interesting part is that the solution ...
14
votes
2answers
14k 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 ...
14
votes
2answers
6k 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 ...
14
votes
1answer
622 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-...
14
votes
2answers
576 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 ...
14
votes
1answer
2k 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 ...
14
votes
1answer
223 views

Are runtime bounds decidable for anything nontrivial?

Problem  Given a Turing machine $M$ which has known runtime ${O}(g(n))$ with respect to input length $n$, is the runtime of $M \in {O}(f(n))$? Is the above problem decidable for some ...
14
votes
2answers
3k views

Set Similarity - Calculate Jaccard index without quadratic complexity

I have a group of n sets for which I need to calculate a sort of "uniqueness" or "similarity" value. I've settled on the Jaccard index as a suitable metric. Unfortunately, the Jaccard index only ...
14
votes
2answers
464 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 ...
13
votes
4answers
2k views

Has the graph isomorphism problem been solved?

Wikipedia's graph isomorphism problem page would seem to indicate that, no, it has not been solved. However, a friend of mine pointed out A Polynomial Time Algorithm for Graph Isomorphism . I am not ...
13
votes
4answers
42k views

Complexity of recursive Fibonacci algorithm

Using the following recursive Fibonacci algorithm: def fib(n): if n==0: return 0 elif n==1 return 1 return (fib(n-1)+fib(n-2)) If I input ...
13
votes
2answers
16k views

Time complexity of a triple-nested loop

Please consider the following triple-nested loop: ...

1
2 3 4 5
33