New answers tagged time-complexity
3
votes
Are there any problems whose best known algorithms have running time $n^{\log \log n}$?
The best-known algorithm for testing isomorphism of finite groups whose solvable radical is either (a) contained in the center or (b) elementary abelian, is $n^{O(\log \log n)}$. These are, ...
5
votes
Are there any problems whose best known algorithms have running time $n^{\log \log n}$?
The best-known deterministic algorithm for testing polynomial identities given by depth-three diagonal circuits has running time $n^{O(\log \log n)}$ [1].
More explicitly, we are given an expression ...
0
votes
Selecting unique records from a large dataframe with many duplicate records
In the context of Theoretical Computer Science, there are various strategies to (quickly) select the unique elements of a list, mainly comparison based and value based.
Value based: If computing a ...
1
vote
What is the problem in "closest pair problem" if all points share the same x-coordinate
Without the assumption that no points share the same x-coordinate, we run into one of two problems:
One problem occurs if you partition the space by x-coordinate. Say all points have the same x-...
3
votes
Solving All-Pairs Shortest Paths using a distance matrix in sub-cubic time
The discussion in this paper, Section 3 beginning on page 7, might be useful to you. It focuses on reducing distance product witnesses to distance product, which is the same as distance vs path APSP ...
9
votes
Lower-bounds under SETH
Most problems need at least linear time, so $O(n \log n)$ may be a little too close to optimal for a SETH based lower bound, generally we want running times where one can improve on the exponent by ...
Top 50 recent answers are included
Related Tags
time-complexity × 357cc.complexity-theory × 136
ds.algorithms × 88
complexity-classes × 36
reference-request × 30
graph-algorithms × 24
lower-bounds × 22
space-complexity × 19
graph-theory × 16
polynomial-time × 16
ds.data-structures × 15
optimization × 13
turing-machines × 13
linear-algebra × 12
np-hardness × 11
sat × 11
matrices × 11
sorting × 11
nt.number-theory × 10
time-hierarchy × 10
fl.formal-languages × 8
quantum-computing × 8
automata-theory × 8
circuit-complexity × 8
counting-complexity × 8