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
2
votes
1answer
3k views

how to solve NFA acceptance problem in polynomial time

I need to show that the language Anfa = {(A,w)| A is an nondeterministic finite automata that accepts w} can be decided in polynomial time. My problem is every solution that I think of requires ...
2
votes
1answer
75 views

How do we prove the time complexity of this simple problem in probabilistic inference on a Bayesian network?

Suppose we have a simple Bayesian network with two rows of nodes: $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_n$. Each node $x_k$ takes a state of either 0 or 1 with equal probability. Each ...
1
vote
3answers
113 views

Dividing 2 integers with some constraints

This a problem i came across while practicing binary search. Here is the problem: Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. ...
0
votes
1answer
552 views

Time complexity of mutually recursive functions

Suppose I have two mutually recursive functions like this: ...
0
votes
1answer
490 views

Psedu-polynomial Time : Conflict with the definition of input size

From wikipedia In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the length of the input (the number of bits required ...
0
votes
1answer
658 views

What is the complexity of the problem of computing the cardinality of the union of many (finite) and small sets?

What is the complexity of the problem of computing the cardinality of the union of many (finite) and small sets? What is both the time and space complexity of the naive algorithm that does this ...
-2
votes
2answers
2k views

complexity of decision problems vs computing functions [closed]

This is an area that admittedly I've always found subtle about CS and occasionally trips me up, and clearly others. recently on tcs.se a user asked an apparently innocuous question about N-Queens ...
7
votes
12answers
12k views

Time complexity of min() and max() on a list of constant size?

If you use min() or max() on a constant sized list, even in a loop, is the time complexity O(1)?
7
votes
2answers
376 views

Transforming an array into one with descending order

Problem Description Given an array $A$ of $n$ integers, find the minimum number of operations to turn it into a new array $\widehat{A}$ with a (weakly) descending order: we require that $\hat{a}_i \...
7
votes
2answers
2k views

Can you do an in-place reversal of a string on a vanilla turing machine in time $o(n^2)$?

By a vanilla Turing machine, I mean a Turing machine with one tape (no special input or output tapes). The problem is as follows: the tape is initially empty, other than a string of $n$ $1$s and $0$s ...
6
votes
1answer
355 views

What is the complexity of this subset merge algorithm?

Updated Algorithm: There was a major flaw in my original presentation of the algorithm which could have impacted the results. I apologize for the same. The correction has been posted underneath. The ...
5
votes
2answers
192 views

Can this system of polynomial equations be solved in polynomial time?

I have these $n$ equations, with $n$ variables. Variables are first $n$ positive integers, constants can be any rational number including zero. Given that there is always a solution, how do we find a ...
5
votes
2answers
575 views

Do I need to consider instance restrictions when showing a language is in P?

I have already shown that 3-colorable for an unrestricted graph is in NP, but I was thinking about the similar language defined as the set of all acyclic $G$, where $G$ such that $G$ is 3-colorable. ...
5
votes
6answers
3k views

Can every algorithm's running time be expressed as $\Theta(f(n))$?

That is, can the running time of every algorithm $A$ be written as $O(f_A(n))$ and $\Omega(f_A(n))$, for the same function $f_A$?
4
votes
3answers
691 views

Complexity of Independent Set on Triangle-Free Planar Cubic Graphs

I know that IS (is there independent set of size at least $k$?) on planar cubic graphs is NP-Complete, and IS on triangle-free graphs is also NP-Complete. But how about IS on triangle-free planar ...
4
votes
1answer
203 views

Is matrix "adjoint-squaring" faster than general matrix multiplication?

The best known algorithm(s) for matrix multiplication of $n$-dimensional matrices take $O(n^{2.37})$ time. However, that's for matrices with totally independent contents. When the two matrices are ...
4
votes
2answers
1k views

What complexity class would this version of generalized chess fall?

By now I understand that generalized chess is harder than NP, and is EXPTIME-complete for the decision problem "Given an nxn board with a given position, can white force a win?" because the proof ...
4
votes
1answer
1k views

Lower-bound complexities for finding common elements between two unsorted arrays

I'm facing some problems that deal with finding common elements between unsorted arrays and I'd like to know whether there are well-known lower-bounds for the worst-case and, eventually, what are ...
4
votes
1answer
535 views

Using hash tables instead of lists for buckets in hash tables

Say instead of using a linked list as buckets for a hash table of size $m$, we use another hash table of size $p$ as buckets this time. What would be the average case for this problem? I looked up ...
4
votes
0answers
105 views

How hard is recovering an invertible binary matrix from its check sums?

This is a follow-up question on my previous one, How hard is recovering a binary matrix from its check sums?. Consider the following problem, which adds an extra restriction that the matrix be ...
4
votes
1answer
528 views

Will the Traveling Salesman Problem (TSP) become easier if the simple path constraint is omitted?

Will the Traveling Salesman Problem (TSP) become easier if the simple path constraint is omitted? That is, each node in the topological graph should be visited once at least (instead of exactly). Is ...
4
votes
1answer
50 views

On complexity of the sieve, start crossing at the square of $p$

This question is about a common optimization in the basic sieve of Erathostenes. If we look at this paper (page 3, footnotes), the author says: If we start crossing off at $p^2$ rather than $p$, ...
3
votes
2answers
948 views

Time Complexity: Why does $n^n$ grow faster than $n!$?

Seeing the title, you will probably like to give your explanation as $n!=n\times (n-1)\times (n-2)\times (n-3)\times\cdots\times 1$ where as $n^n$ = $n\times n \times n\times n \times\cdots\times ...
3
votes
1answer
380 views

Is it axiomatic that the Time Hierarchy Theorem holds true in all relativized worlds?

I learned from this post that ${\sf DTIME}^{\text{EXP}}(n^k) \neq \text{EXP}$ for a fixed $k$ for otherwise the Time Hierarchy Theorem would fail in that relativized world. However, is it possible to ...
3
votes
0answers
112 views

Are there any algorithms where the recovery of a witness changes the time complexity?

In many algorithms, such as the solution to the longest-subsequence problem using dynamic programming, finding the length of an answer (or signaling the nonexistence of an answer) is easy, but ...
3
votes
0answers
101 views

Generalizing Matrix Chain problem: optimal summation in a tree

Matrix Chain Problem can be viewed as the problem of finding the optimal summation order in a path-structured tensor network. How hard is the problem if we extend it to trees? For instance, take the ...
3
votes
0answers
260 views

Is it possible to compute an equality hash for nodes in a *cyclic* directed graph in less than quadratic time?

Calculating hashes for nodes in an acyclic graph is well known using a Merkle tree. With some simplifying assumptions, a simple algorithm will also calculate hashes for nodes in a cyclic graph... but ...
3
votes
5answers
9k views

Most efficient known priority queue for inserts

In terms of asymptotic space and time complexity, what is the most efficient priority-queue? Specifically I am looking for priority queues which minimize the complexity of inserts, it's ok if deletes ...
3
votes
1answer
1k views

Proving that NPSPACE $\subseteq$ EXPTIME

I am following "Introduction to the theory of computation" by Sipser. My question is about relationship of different classes which is present in Chapter 8.2. The Class PSPACE. $P \subseteq NP \...
3
votes
1answer
140 views

Hierarchy of complexity classes $\bigcup_{c > 0} \mathrm{Time}(2^{c \log^k n})$, w.r.t. $k$

This is a true/false question: For each integer $k > 1$, define the complexity class $\sf QP_k := \bigcup_{c > 0} Time(2^{c \log^k n})$. Then for all integers $k > 1$, $\sf QP_k \subsetneq ...
3
votes
1answer
989 views

Is there a decision algorithm with time complexity of Ө(n²)?

Is there a decision problem with a time complexity of Ө(n²)? In other words, I'm looking for a decision problem for which the best known solution has been proven to have a lower bound of N². I ...
3
votes
3answers
1k views

How to write a recursive function that with certain time complexity

I'm now doing exam revision, and from some past year exam papers, I noticed some questions that ask to write a recursive method with signature like ...
3
votes
1answer
56 views

surprizing reducibility and challenge on it

Assume that Problem $A$ is polynomial-time reducible to problem $B$. Claim 1: If problem $A$ is NP-hard then problem $B$ is NP-hard. Claim 2: If problem $B$ is NP-hard then problem $A$ is NP-hard. ...
3
votes
1answer
2k views

Complexity of a recursive bignum multiplication algorithm

We have started learning about analysis of recursive algorithms and I got the gist of it. However there are some questions, like the one I'm going to post, that confuse me a little. The exercise ...
2
votes
1answer
15k views

What does a polynomial time reduction mean?

I am having a little trouble understanding what is meant by a poly-time reduction. Suppose I have two algorithms $A$ and $B$ and then I say that $A$ is reducible to $B$. Does polytime reduction mean ...
2
votes
1answer
127 views

How to compare n number of m-dimensional points among one another with minimum time complexity?

Suppose there are four points (n = 4) which are four dimensional (m = 4) . Lets say these points are : A(4,1,1,1) , B(3,2,1,1) , C(2,3,3,3) , D(1,4,4,4). What is the best data structure to compare all ...
2
votes
1answer
95 views

largest samples of set of random variables

Suppose we have two discrete random variables and we want perform maximum operation to obtain the max PDF. We know that max of two independent random variables is: if $Z = max(X,Y)$ $pr(Z = k) = pr(...
2
votes
1answer
436 views

Finding asymptotically tight bounds $\Theta$ of two procedures

I would like to check time complexity of two procedures for which I am not totally convinced that I got it right. Now the first procedure is this: ...
2
votes
2answers
562 views

Check if K-Sum Variation is NP-Complete

Problem Given a range of integers $\{a,a+1,...,b-1,b\}$, find a subset of size $k$ such that the sum is equal to $s$. Question This problem came from evaluating some scheduling algorithms that I am ...
2
votes
1answer
492 views

$T(n) = \sqrt{n}\,T(\sqrt{n}) + n\log n$ [duplicate]

I tried to solve the recurrence $T(n) = \sqrt{n}\,T(\sqrt{n}) + n\log n$ with the master theorem but I can't get it to work. How many arrays exist in each step in the recursion tree? Or can I solve ...
2
votes
3answers
2k views

If A is in P and B is non-trivial, then A ≤p B [duplicate]

On wikipedia's article on Polynomial-time reduction it states: Every nontrivial decision problem in P (the class of polynomial-time decision problems, where nontrivial means that not every input ...
2
votes
1answer
734 views

What is the precise definition of pseudo-polynomial time (feat. Counting Sort)

From wikipedia In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the length of the input (the number of bits required ...
2
votes
1answer
367 views

efficient algorithm for min cut with specified number of vertices

Consider a graph with vertices $V$ and edges $E$. The standard version of the min cut problem is to find the partition of $V$ into a (non-empty) subset $C$ and its complement $\bar{C}$ so as to ...
2
votes
0answers
253 views

A question about $O(T \log T)$ simulation of a TM on some input by universal turing machine

In the textbook by Arora and Barak in Chapter 1 and section 1.7 they have proved how a UTM can do simulation in $O(T \log T)$ time. I have read it and understood everything except that how the $k$th ...
2
votes
1answer
590 views

A special case for the subset sum problem

If we wanted to see if any disjointed subset of a set $X = [w_1, ..., w_n]$ exists such as the sum of its elements equal exactly a given value $M$ (0-1 Knapsack problem) we could employ a DP solution ...
2
votes
1answer
1k views

What is the correct way to define time constructible functions?

Sipser defines a time constructible function as $f(n)$ is time constructible if there exists a turing machine which given input $1^n$ writes value of $f(n)$ in binary to the output tape in $O(f(n))$...
2
votes
1answer
352 views

What is the lower bound for finding the third largest in a set of $n$ distinct elements?

What is the lower bound for finding the third largest in a set of $n$ distinct elements? For the case of finding the second largest, we have the tight lower bound of $n + \lceil \lg n \...
2
votes
3answers
288 views

Algorithm to identify top $\log n$ elements in $O(n)$ time

Airlines has a new policy to give a first-class upgrade coupon to their customers based on the number of miles accumulated. They decided to give it to their top $\log(n)$ frequent flyers, where n is ...
2
votes
1answer
2k views

Base of logarithm in runtime of Prim's and Kruskal's algorithms

For Prim's and Kruskal's Algorithm there are many implementations which will give different running times. However suppose our implementation of Prim's algorithm has runtime $O(|E| + |V|\cdot \log(|V|)...
2
votes
2answers
520 views

Common Algorithms without Asymptotically Tight Bounds

I can think of functions such as $n^2 \sin^2 n$ that don't have asymptotically tight bounds, but are there actually common algorithms in computer science that don't have asymptotically tight bounds ...