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.)

Filter by
Sorted by
Tagged with
0
votes
1answer
1k views

Near-Sort quicksort algorithm faster than O(nlgn) [closed]

Here, we define a nearly-sorted array with k-sized error, as this: Elements in the array may be in the wrong order, but only if they are not distanced by more than k indices. For example: 1, 2, 3, 6, ...
6
votes
2answers
2k views

Complexity of the halting problem

One of the most celebrated results in computer science is that the halting problem is undecidable. However there are still notions of complexity that are applicable. Here are 3 that I have in mind: $...
4
votes
0answers
173 views

Complexity of computing logarithm of a prime power

Suppose $n = p^k$ for some prime number $p$ and some non-negative integer $k$. What is (the best-known upper bound on) the complexity of computing $k$ on input $n$ (given in binary)? It is important ...
8
votes
0answers
161 views

Cell probe model vs transdichotomous ram

can someone explain me the difference between those two (cell probe model and transdichotomous ram)? In cpm I'm allowed to do computation for free, and complexity of algorithm is just a number of ...
3
votes
1answer
2k views

Computational complexity of classifying with an already-trained SVM

If I have a support vector machine which has already been trained, what is the computational complexity of classifying a new example using that machine? I care about both time and space complexity. ...
15
votes
3answers
2k views

Linear time in-place riffle shuffle algorithm

Is there a linear time in-place riffle shuffle algorithm? This is the algorithm that some especially dextrous hands are capable of performing: evenly dividing an even-sized input array, and then ...
7
votes
0answers
241 views

How quickly can we find an arbitrary digit in multiplication?

In considering an answer to this question, I once again wondered how quickly we could find a digit in multiplication. We may first consider previous results. Finding the least significant digits is ...
16
votes
2answers
286 views

similar matrices

Given two $n \times n$ matrices $A$ and $B$, the problem of deciding if there exist a permutation matrix $P$ such that $B = P^{-1}AP$ is equivalent to GI(Graph ...
21
votes
1answer
2k views

Is there a proof that addition is faster than multiplication?

The best upper bound known on the time complexity of multiplication is Martin Fürer's bound $n\log n2^{O(\log^* n)}$, which is more than linear time complexity of addition. Do we have a proof that ...
2
votes
0answers
502 views

Tricky big-O calculation

I have a recursive algorithm in which the time for each step depends on the time for smaller steps. Essentially a structure is built at steps 1, 2, ..., n which must be searched at larger heights: $$ ...
23
votes
2answers
1k views

To what extent can an algorithm predict the time complexity an arbitrary input program?

The Halting problem states that it is impossible to write a program that can determine if another program halts, for all possible input programs. I can, however, certainly write a program that can ...
5
votes
0answers
758 views

Does L=P imply any new complexity class separations?

If L=P then P is not equal to PSPACE. This follows from PSPACE properly containing L. I am wondering if L=P implies any stronger separation between complexity classes? Does it imply P is properly ...
4
votes
2answers
165 views

Function with space-depending computation time

Does a function exist which is easily computable for one space capacity and is hard to compute for another? I am looking for a function which can be computed in polytime when available space is at ...
0
votes
1answer
382 views

$\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ for some $g \in o(n^k)$?

Can this statement be confirmed or disproved: $\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ for some $g \in o(n^k)$ [Question changed to use Kaveh's brilliant formulation.] Here the NDTM ...
13
votes
2answers
807 views

Gaussian Elimination in terms of Group Action

Gaussian elimination makes determinant of a matrix polynomial-time computable. The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to ...
6
votes
2answers
238 views

Vertex subset of maximum size

I was wondering if this problem has a name and/or it has been already studied. Problem: Given an undirected graph $G=(V,E)$, a function $f: V \to \mathbb N$, and a natural number $k$ : Does ...
13
votes
0answers
521 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)$ ...
6
votes
1answer
131 views

Can we do joins in NC?

Suppose we want to join two relations on a predicate. Is this in NC? I realize that a proof of it not being in NC would amount to a proof that $P\not=NC$, so I'd accept evidence of it being an open ...
2
votes
0answers
316 views

What's the complexity of Spearman's rank correlation coefficient computation? [closed]

I've been studyin' the Spearman's rank correlation coefficient. If computed for two list that have both size $N$, what's the complexity of the algorithm? $O(N)$ ? Thanks in advance.
14
votes
1answer
5k views

The computational complexity of matrix multiplication

I am looking for information about the computational complexity of matrix multiplication of rectangular matrices. Wikipedia states that the complexity of multiplying $A \in \mathbb{R}^{m \times n}$ by ...
7
votes
3answers
1k views

Algorithms with finite expected running time and infinite variance

I am working on an algorithm for which the running time is a random variable $X$ that has finite expected value, but infinite variance. Are there examples of other algorithms for which this is the ...
-11
votes
2answers
3k views

Are sorting algorithms approaching linear time? [closed]

I see some algorithms can do sorting in O(nloglogn) time. Is it reasonable to assume that as research progresses, more and more will be done to logarithm the extra time e.g. next research will produce ...
1
vote
1answer
1k views

Worst-case asymptotic-complexity of the Set-cover problem?

What's the worst-case asymptotic-complexity of the Set-cover problem in Big O notation? I've been developing some novel techniques to try and solve this problem but am having trouble finding the ...
3
votes
1answer
258 views

Minimum length walk from s to t covering a subset of vertices

I want to find the current literature for the following problem (I have searched on google/asked friends/some Profs didn't get much useful results yet): Input: weighted undirected graph G = (V,E), $...
8
votes
0answers
1k views

Is there an ambiguity test for CFGs faster than trying all strings?

It is well known that testing whether a grammar is ambiguous is undecidable. It is however trivially decidable for any $G$ whether $L_n(G) := \{ w | w \in L(G) \wedge |w| \leq n \}$ for any $n \in \...
5
votes
1answer
1k views

Optimality of Greedy algorithm for minimization Knapsack Problem

Given items with weight $w_i$ and profits $p_i$, minimization Knapsack problem is to pick a subset of items $I$, s.t. $\sum_{i\in{I}}{w_i} \geq W$ and $\sum_{i\in{I}}{p_i}$ is minimized. The greedy ...
2
votes
3answers
3k views

Complexity of greedy coloring

I was looking at some heuristics for coloring and found this book on Google books: Graph Colorings By Marek Kubale They describe the Greedy algorithm as follows: ...
1
vote
0answers
627 views

“Exact” (not just the order) computational complexity of eigenvalue decomposition

Does anyone know what the eigenvalue decomposition of a general n x n complex matrix is? By complexity I mean the number of multiplication operations. I know from another question posted on this site ...
6
votes
1answer
362 views

Complexity of the directed Steiner tree problem on special graph classes

I am interested in the complexity of the directed Steiner tree problem: Given a weighted digraph $D=(V,E)$, a root $r\in V$ of $D$, and a set of terminals $T\subseteq V$. The objective is to find a ...
2
votes
1answer
84 views

Lower bounds on batched query search

I am not much in the field of databases. But the problem I m facing is the following: given a database $D$, we receive a batch of distinct queries $Q = \{q_1, ..., q _k\}$, where each $q_i$ is a ...
-1
votes
1answer
333 views

How can a problem have complexity $O(n^{2+\epsilon})$ for all $\epsilon > 0$?

For instance, it is believed that for any $\epsilon>0$ there is an algorithm for matrix multiplication that runs in $O(n^{2+\epsilon})$, but possibly no algorithm that runs in $O(n^2)$. How is this ...
0
votes
0answers
186 views

Indexing over all possible functions in better than linear time

Given two sets X and Y, the number of functions mapping X to Y is $\vert Y\vert^{\vert X \vert}$. In particular I am interested in binary strings of relatively small length, e.g. 8. There are $2^8$ (...
1
vote
0answers
296 views

NP-Completeness of Certain Bounded Degree Graphs [closed]

I was studying time complexity when it comes to bounded degree graph problems and I was wondering if I can get help with the following two problems. 1) Is the set of all (G, k) where G is a graph ...
3
votes
0answers
211 views

Optimal term frequency analysis

I'm looking for a term-frequency analysis structure which is more efficient than a hash table in terms of worst-case performance and speed in practice. I specifically care about the operations insert ...
22
votes
1answer
2k views

Can all unambiguous grammars be parsed in linear time?

When tinkering with noncanonical LR parsing, I thought up a parsing method (with infinitely sized tables, which makes it somewhat unpractical) capable of parsing exactly the unambiguous grammars in $O(...
-3
votes
1answer
272 views

How many steps does this recurrence take to get to 2 (or 1)?

$T(2) = T(1) = 1$ $T(n) = T(\frac{n}{\log n}) + \Theta(1)$ Basically, I wanted to know how many steps before the recursion stops? I tried various approaches, but am not getting anywhere. I know for ...
12
votes
5answers
1k views

Are there decidable problems for which for no algorithm we can give time bounds?

Are there decidable problems such that for no algorithm which solves the problem we can give a time bound as a function of the length n of the input instance? I arrived at this question because I was ...
7
votes
3answers
636 views

Different definitions of complexity

I'm a math student and have encountered the concept of (mainly time) complexity of algorithms in several courses so far (Analysis of Algorithms, Cryptography, Numerical Analysis). However what strikes ...
6
votes
1answer
346 views

Solving multiple instances of 3SUM generated from the same set

(this is a follow-up of my previous question, which uses the 3SUM' problem instead of 3SUM) Suppose we have a list $S$ of $n$ integers. Usually, for 3SUM, we only determine if there exist $a$,$b$,$c$ ...
7
votes
0answers
249 views

Complexity of reachability in Markov Chains

Is anything known about the complexity of the following problem beyond membership in PTIME: Given a finite Markov chain $M$, an initial state $q_0$ and a set $F$ of (absorbing) states, is the ...
10
votes
1answer
680 views

Fastest known algorithm for finding simple paths through given set of vertices

For an undirected graph $G$ and a given set $S$ of vertices, what is the asymptotically fastest known algorithm for finding a simple path containing all elements of $S$. What if we require the path to ...
12
votes
2answers
727 views

Complexity of Membership-Testing for finite abelian groups

Consider the following abelian-subgroup membership-testing problem. Inputs: A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with arbitrary-...
0
votes
2answers
567 views

What is the problem in “closest pair problem” if all points share the same x-coordinate

The closest pair of points problem deals with the task to find a pair of points with the global minimum distance. There is a problem, when all points share the same x-coordinate, or at least a large ...
13
votes
1answer
668 views

Is Quasi-polynomial time in PSPACE?

I had done some search on this but I was not able to find an answer either way. Huck answered it fully. Thanks :)
7
votes
1answer
269 views

Trade off between time and query complexity for total functions

This is a continuation of an earlier question on the trade off between time and query complexity. By a trade off we consider the following two types of algorithms: The best query algorithm: this ...
5
votes
1answer
503 views

Consequences of a $O^*(2^{n / \log(n \log n)} )$ algorithm for a #P-complete problem

Question Suppose that there exist a deterministic algorithm for solving a #P-complete problem in time $O^*(2^{n / \log(n \log n)})$. What would be the theoretical consequences of such a fact? ...
-1
votes
3answers
748 views

Examples for $\Theta(n^n)$ problems

I was just wondering if there is a problem whose best solution (under common assumptions) has time complexity $\Theta(n^n)$. And what complexity class would that belong to?
18
votes
2answers
5k views

Complexity of computing the discrete Fourier transform?

What is the complexity (on the standard integer RAM) of computing the standard discrete Fourier transform of a vector of $n$ integers? The classical algorithm for fast Fourier transforms, ...
6
votes
3answers
919 views

Complexity lower bound for regular languages

Suppose I have a regular language $L$, and I would like to lower-bound the complexity of deciding membership in $L$. Suppose I know that the minimal DFA for $L$ has $N$ states. I would like to claim ...
2
votes
1answer
377 views

Arthur-Merlin protocol with BQP power

Context: Aaronson raised the following question: Let f be a black-box function, which is promised either to satisfy the Simon promise or to be one-to-one. Can a prover with the power of BQP ...