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 [tag:runtime-analysis] instead. If your question concerns whether or not a computation will *ever* finish, use [tag:computability] instead. Time-complexity is perhaps the most important sub-topic of [tag:complexity-theory].

Filter by
Sorted by
Tagged with
12
votes
2answers
3k views

If lower bound of a problem is exponential then is it NP?

Assuming that we have a problem $p$ and we showed that the lower bound for solving $p$ is $\mathcal{\Omega}(2^n)$. can lower bound $\mathcal{\Omega}(2^n)$ implies the problem in $NP$?
12
votes
2answers
2k 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 ...
12
votes
3answers
4k views

How fast can we find all Four-Square combinations that sum to N?

A question was asked at Stack Overflow (here): Given an integer $N$, print out all possible combinations of integer values of $A,B,C$ and $D$ which solve the equation $A^2+B^2+C^2+D^2 = N$. This ...
12
votes
3answers
343 views

Why larger input sizes imply harder instances?

Below, assume we're working with an infinite-tape Turing machine. When explaining the notion of time complexity to someone, and why it is measured relative to the input size of an instance, I ...
12
votes
4answers
966 views

Does the complexity of strongly NP-hard or -complete problems change when their input is unary encoded?

Does the difficulty of a strongly NP-hard or NP-complete problem (as e.g. defined here) change when its input is unary instead of binary encoded? What difference does it make if the input of a ...
11
votes
4answers
23k views

Evaluating the average time complexity of a given bubblesort algorithm.

Considering this pseudo-code of a bubblesort: ...
11
votes
2answers
555 views

Is HORN-SAT in LIN, if so why is that not an indication that P=LIN?

The Complexity Zoo defines $LIN$ to be the class of decision problems solvable by a deterministic Turing machine in linear time. $$LIN \subseteq P$$ Since HORN-SAT is solvable in $O(n)$ (as ...
11
votes
3answers
2k 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: ...
11
votes
2answers
2k 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 in this case, I'm interested in the algorithm that solves a given problem using the least number of steps. We would therefore ...
11
votes
1answer
6k 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 ...
11
votes
2answers
3k views

Hashing using search trees instead of lists

I am struggling with hashing and binary search tree material. And I read that instead of using lists for storing entries with the same hash values, it is also possible to use binary search trees. And ...
11
votes
1answer
867 views

Collection of APX-hard problems

Everyone knows "Garey & Johnson", which is my go-to reference whenever I need a problem to transform from for an NP-hardness proof. However I recently find myself in need of an APX-hardness proof, ...
11
votes
1answer
193 views

Does a subcubic algorithm exist for the following problem?

Given a symmetric real $n \times n$ matrix $A=(a_{ij})$, is there an algorithm which computes the sum $$\sum_{i,j,k}\max(a_{ij},a_{ik},a_{jk})$$ over all $1\leq i<j<k\leq n$ with time-complexity ...
10
votes
2answers
4k views

Contradiction proof for inequality of P and NP?

I'm trying to argue that N is not equal NP using hierarchy theorems. This is my argument, but when I showed it to our teacher and after deduction, he said that this is problematic where I can't find a ...
10
votes
1answer
819 views

Why isn'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 ...
10
votes
2answers
2k views

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

I've been studying the Spearman's rank correlation coefficient $\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2 \sum_i(y_i-\bar{y})^2}}$. for two ...
10
votes
3answers
21k views

A d-ary heap problem from CLRS

I got confused while solving the following problem (questions 1–3). Question A d-ary heap is like a binary heap, but(with one possible exception) non-leaf nodes have d children instead of 2 ...
10
votes
1answer
192 views

Could this be an NP-Complete problem?

Consider the following problem statement: Given an initial number, you and your friend take turns to subtract a perfect square from it. The first one to get to zero wins. For example: ...
10
votes
3answers
634 views

Proving that if $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$

I'd really like your help with proving the following. If $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$. Here, $\mathrm{NTime}(n^{100})$ is the class of ...
10
votes
1answer
227 views

Computing the number of bits of a large power of integer

Given two integers $x$ and $n$ in binary representation, what is the complexity of computing the bit-size of $x^n$? One way to do so is to compute $1+\lfloor \log_2(x^n)\rfloor=1+\lfloor n\log_2(x)\...
9
votes
6answers
3k views

Are there variations of the regular runtimes of the Big-O-Notation?

There are multiple $O$-Notations, like $O(n)$ or $O(n^2)$ and so on. I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log n^2)$, or if those are mathematically ...
9
votes
3answers
2k views

Does Quicksort always have quadratic runtime if you choose a maximum element as pivot?

If you have a quick-sort algorithm, and you always select the smallest (or largest) element as your pivot; am I right in assuming that if you provide an already sorted data set, you will always get ...
9
votes
1answer
517 views

Is there an algorithm for algorithms time/space complexity optimisation?

In 1950s a number of methods for circuit minimization for Boolean functions have been invented. Is there an extension of those methods or anything similar for optimising time or space complexity of ...
9
votes
2answers
4k views

Time Complexity of Genetic Algorithms

How do you determine the Time Complexity of a Genetic Algorithm(in general)? If possible. I have been thinking about this a lot, and all of the teaching I have had is related to determining the Time ...
9
votes
2answers
826 views

Why do we say that polynomial time is easy? [duplicate]

For years, I've been told (and I've been advocating) that problems which could be solved in polynomial time are "easy". But now I realize that I don't know the exact reason why this is so. ...
9
votes
2answers
433 views

Do there exist “O(1)-complete” problems?

Many complexity classes have "complete" problems. Do complete problems exist for the complexity class of problems that can be solved in $O(1)$ time? A complication is that this class depends on the ...
9
votes
1answer
387 views

How to measure the complexity of the discrete logarithm problem?

The answers to this question on Crypto Stack Exchange basically says that, to measure the complexity of the logarithm problem, we have to take the length of the number representing the size of the ...
9
votes
2answers
5k 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(\...
9
votes
1answer
164 views

Influence of the dimension of cellular automata on complexity classes

Let's take as an example the 3d → 2d reduction: What's the cost of simulating a 3d cellular automaton by a 2d cellular automaton? Here is a bunch of more specific questions: What kind of algorithms ...
9
votes
1answer
1k views

NTIME(f) subset of DSPACE(f)

As the question states, how do we prove that $\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n))$? Can anyone point me to a proof or outline it here? Thanks!
9
votes
1answer
243 views

Can joins be parallelized?

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 ...
9
votes
0answers
281 views

P vs NP and the Time Hierarchy

Assuming $P\neq NP$, is it possible that there exists a $k$ such that $P\subseteq\textsf{NTIME}(t^k)$? There reason I ask this is that I assume the following: $$P=NP \implies \forall k\ \exists j.\ \...
8
votes
2answers
4k views

Shor's Algorithm speed

I'm a fledgling computer science scholar, and I'm being asked to write a paper which involves integer factorization. As a result, I'm having to look into Shor's algorithm on quantum computers. For ...
8
votes
1answer
647 views

Prove or refute: BPP(0.90,0.95) = BPP

I'd really like your help with the proving or refuting the following claim: $BPP(0.90,0.95)=BPP$. In computational complexity theory, BPP, which stands for bounded-error probabilistic polynomial time ...
8
votes
1answer
317 views

Checking whether the win-loss standings of a league are possible

You're hosting a 1 v 1 basketball league with a game schedule. At the end of the league you have each player report their supposed win-loss record (there are no ties), but you want to check whether ...
8
votes
1answer
334 views

Following yesterday's StackOverflow outage - is regular expression matching really difficult, or is the implementation simply inefficient?

Yesterday StackOverflow was down for half an hour. Later, they wrote a blog post about it, detailing that the problem stemmed from unexpectedly high complexity of regular expression matching. In ...
8
votes
2answers
143 views

Is there always a Big Oh complexity strictly between any two others?

I'm learning about asymptotic analysis, and have seen some exotic looking complexities living between other common ones. For instance "log log n" is strictly between 1 and log n. It makes me wonder if ...
8
votes
1answer
105 views

Is writing a number as two squares and writing the factors of a number equally hard?

Let $L_1$ and $L_2$ be the following: $L_1=\{r:\exists x,y \in \mathbb{Z} \text{ such that } x^2+y^2=r\}$ $L_2=\{(N,M): M<N, \exists 1<d\leq M \text{ such that d|N} \}$ Claim $L_1 \leq_P ...
8
votes
2answers
846 views

Could a quantum computer perform linear algebra faster than a classical computer?

Supposing we had a quantum computer with a sufficient number of qubits, could we use it to do linear algebra faster than we could with a classical computer? What sort of speedup could we expect? Has ...
8
votes
1answer
96 views

Complexity class that properly included in DLOGTIME

Is there any decision problem that is in a complexity class properly included in DLOGTIME? (except $O(1)$, of course) If there is, can we create complete problems for DLOGTIME? So, can there be ...
8
votes
1answer
603 views

Prove n! is fully time constructible

We just finished our "Time constructability" lesson in class last week, and we, for example's sake, showed that $n^k, 2^n$ are fully time constructible, i.e. there exists a (multi-tape deterministic) ...
8
votes
1answer
220 views

Maximum Stacking Height Problem

Has the following problem been studied before? If yes, what approaches/algorithms were developed to solve it? Problem ("Maximum Stacking Height Problem") Given $n$ polygons, find their stable, ...
8
votes
1answer
236 views

NEXP = Σ$_2$ ⟹ NEXP = MA?

Is it known whether the implication $\mathsf{NEXP} = \Sigma_2 \implies \mathsf{NEXP} = \mathsf{MA}$ holds? (The question is inspired by well-known $\mathsf{NEXP} \subseteq \mathsf{P/poly} \...
8
votes
0answers
122 views

Complexity of removing edges to eliminate a perfect matching

Suppose $G$ is a bipartite graph which has a perfect matching. I want to find the fewest number of edges to delete from $G$ so that a perfect matching no longer exists. What is the complexity of this ...
8
votes
0answers
873 views

Complexity of Sorting Integers on a Multitape Turing Machine

How expensive is sorting integers on a Multitape Turing Machine? Well known sorting algorithms, like quicksort, tend to rely on jumping / indirect-access being cheap. But MTMs have no indirect access.....
7
votes
4answers
3k views

Simple (non-mathematical) definition of polynomial time?

Computational Complexity Theory is complex. My understanding of polynomial time is in relation to other time complexity classes, such as non-deterministic polynomial time. This is fine for engineers ...
7
votes
6answers
3k views

Can a subset of an NP-complete problem be in P?

The problem is NP-complete (proven) for all input data (without exception). We assume that P != NP. Is it possible that there is an (infinitely large) subset of the problem, for which this subset is ...
7
votes
2answers
2k views

Is there an polynomial time algorithm to find that sum of square-roots is less than an integer?

Given: A list of $n$ integers $x_1,x_2,\dots,x_n$ and an integer $k$. Determine: Is $\sqrt x_1 + \sqrt x_2 \cdots \sqrt x_n \le k$? Question: Is there any polynomial time algorithm for the above ...
7
votes
4answers
372 views

Does the time complexity of a problem change with encoding of the problem?

Suppose I have a decision problem $D$ and I encode it to a language $L \subset \{0,1\}^*$. Now, I can also encode it to a different language $L'$. Is there any theorem relating the time complexity of ...
7
votes
3answers
5k views

Complexity of finding the largest $m$ numbers in an array of size $n$

What follows is my algorithm for doing this in what I believe to be $O(n)$ time, and my proof for that. My professor disagrees that it runs in $O(n)$ and instead thinks that it runs in $\Omega(n^2)$ ...

1 2 3 4 5 32