Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [time-complexity]

Time complexity of decision problems or relations among time-bounded complexity classes. (Use [tag:analysis-of-algorithms] for the time taken by particular algorithms.)

12
votes
4answers
1k views

Counting the number of vertex covers: when is it hard?

Consider the #P-complete problem of counting the number of vertex covers of a given graph $G = (V, E)$. I'd like to know if there is any result showing how the hardness of such problem varies with ...
10
votes
1answer
2k views

Complexity of converting a boolean circuit to a boolean formula

Given a boolean circuit $C$ on $n$ variables (which uses just NOT,AND and OR gates), what is the most efficient way to extract the boolean formula represented by the circuit? Is there a polytime ...
5
votes
2answers
560 views

Is qsort linear when sorting only two values?

This CodeGolf answer suggests that quick sorting an array whose elements can take only two values is linear. Can this assumption be proved?
6
votes
2answers
1k views

Do runtimes for P require EXP resources to upper-bound? … are concrete examples known? (answer: yes and yes)

Update #6: Wow, quick service on TCS StackExchange! Emanuele Viola has provided an answer Are runtime bounds in P decidable? Answer: No. Emanuele's answer illuminates (for me) Luca Trevisan's ...
7
votes
2answers
293 views

Complexity of summing up integral powers

Let $x$ be a rational number, and $S_n(x)= \sum_{1\leq i\leq n} i^x$. What is the complexity of computing $S_n(x)$ correct to $d$ decimal places? Is this a Hard problem? It is clear from Faulhaber's ...
12
votes
2answers
2k views

Reversing a list using two queues

This question is inspired by an existing question about whether a stack can be simulated using two queues in amortized $O(1)$ time per stack operation. The answer seems to be unknown. Here is a more ...
8
votes
2answers
744 views

What is the initialization time of a link-cut tree?

Link-cut tree is a data structure invented by Sleator and Tarjan, which supports various operations and queries on a $n$-node forest in time $O(\log n)$. (For example, operation link combines two ...
9
votes
1answer
2k views

Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix

This is a specialized version of a previous question: Complexity of Finding the Eigendecomposition of a Matrix . For NxN symmetric matrices, it is known that O(N^3) time suffices to compute the ...
39
votes
6answers
11k views

Complexity of Finding the Eigendecomposition of a Matrix

My question is simple: What is the worst-case running time of the best known algorithm for computing an eigendecomposition of an $n \times n$ matrix? Does eigendecomposition reduce to matrix ...
58
votes
10answers
10k views

One Stack, Two Queues

background Several years ago, when I was an undergraduate, we were given a homework on amortized analysis. I was unable to solve one of the problems. I had asked it in comp.theory, but no ...
8
votes
1answer
880 views

Quickly finding empty-string producing nonterminals in a CFG

For a given context free language G, we call a nonterminal $A_i$ nullable if $A_i \rightarrow^* \epsilon$, ie we can derive the empty string from $A_i$ after applying a finite number of productions. ...
5
votes
1answer
490 views

What is the running time of taking a limit?

I'm interested in finding the running time(s) for determining mathematical limits. For instance, $\lim_{x \to 2} \frac{1}{x} = \frac{1}{2}$. I'd like to know more about algorithms for determining ...
22
votes
1answer
957 views

Binary multiplication and parity convolution

This question is about the relationship between normal multiplication of binary numbers and polynomial multiplication mod 2. To make the question concrete, I would ideally like to know if there is a ...
22
votes
2answers
772 views

Multiplicative version of 3-SUM

What is known about the time complexity of the following problem, which we call 3-MUL? Given a set $S$ of $n$ integers, are there elements $a,b,c\in S$ such that $ab=c$? This problem is similar to ...
8
votes
1answer
537 views

Analysis of the synergy of two algorithms in comparison to their simulation in parallel

Consider the following two algorithms for searching in a sorted array of $n$ elements: A) interpolation search and binary search simulated in parallel, and B) search through alternating ...
0
votes
2answers
3k views

Linked List size in constant time or linear time [closed]

The space-time complexity of getting the size of the linked list can differ in different implementations as far as I understand it. In the Boost C++ library one finds that the size() function can be ...
43
votes
7answers
3k views

Using lambda calculus to derive time complexity?

Are there any benefits to calculating the time complexity of an algorithm using lambda calculus? Or is there another system designed for this purpose? Any references would be appreciated.