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.

2,195 questions
Filter by
Sorted by
Tagged with
37 views

How to evaluate all the binary sequences, generated from $2^{100}$ for finding all the sequeces which contain minimum $10$ zeros?

Suppose I have a set of $2^{n}$ number of binary sequences. And I have to select only those sequences which contain a minimum ${P}$ number of $0$ in it. For example, please consider the below one Eg. ...
9 views

A DFS update without re-running DFS after adding and removing an edge

Given an undirected graph $G=(V,E)$ I perform a DFS run on it, and among other information I get the visit time $s(\cdot )$ and the exit time $f(\cdot )$ per each node and the parent of each node. ...
49 views

Bowyer-Watson Delaunay Triangulation neighbour walk in $O(n^{1/d})$

The Bowyer-Watson Algorithm for creating Delaunay Triangulations works iteratively. Let's say that we have a Delaunay triangulation of $n-1$ points. Now we add the $n$-th point. In order to update the ...
51 views

Maximum independent subset for graphs with lots of edges

Consider an NP-hard graph problem, like the maximum independent set problem. Let us say I restrict my inputs to only be graphs that have $n$ vertices and at least $n^{c}$ edges, for some $c > 1$. ...
13 views

Complexity analysis of a recursion

A recursive algorithm has the following computation tree. The label on the node indicates the number of outgoing edges. This algorithm takes an input of length $n$ and at each processing, it results ...
31 views

Range queries with O(N log N) build and O(1) query

I read somewhere that you can compute range queries in O(1) with O(N log N) preprocessing for any associative operation (but not necessarily invertible or idempotent). How do you do this? I know this ...
16 views

Comparison of Complexity of counting bits in a binary representation

I was asked the following question: Given a number num - write a function (in python) that counts the number of ones in its binary representation. This is the ...
24 views

Are there any complexity classes that can be solved in Polynomial Time that are not in PSPACE?

These would be problems solvable in Polynomial time with and only with pseudo-polynomial or Exponential Space. Do such problems exist? if so which complexity class are they? If not can you prove that ...
15 views

How to find if there's an MST where vertex $v$ has degree 2 in it? [duplicate]

I've faced this question and I hope that someone can help with it. Question: We're given an undirected graph $G=(V,E,w)$ where $w\colon E\rightarrow \mathbb{Q}$ and vertex $v$. We want to find if ...
27 views

Determining runtime of a theoretical program (question of extraordinary complexity)?

I apologize in advance, as I don't have a clue to which stackexchange to post this question! I beg you to not delete this question, as I have chronic pain and it is very important to me!!! I actually ...
18 views

How to prove that some function $f$ is {time,space}-constructible function

Is there a standard method to prove or disprove that some functions are or aren't time or space constructible? can you give me a way to check them ? or an example ?
55 views

Who said first "In practice, log log N is at most (single digit number)?"

In one of my undergrad theory or algorithms classes, I remember a professor sharing a quip that went something like In practice, $\log(\log(N))$ is at most 9. ...the idea being that even though the ...
30 views

How do I determine the time and space complexity of the following algorithm?

I need to compute the time and space complexity in Big O notation for this algorithm I constructed for binary multiplication. ...
18 views

NC with nearest neighbor gates

Consider a circuit belonging to the class $\text{NC}^i$, as defined here. From my understanding, the circuit consists of AND, OR ar NOT gates, each of bounded fan in --- without loss of generality, ...
62 views

Trivial Proof that EXP = PSPACE(im 99% sure i'm doing somthing wrong.)

Generalized chess is EXPTIME complete. Generalized chess is also PSPACE complete. Therefore $EXPTIME = PSPACE$. This implies that $P \neq PSPACE$ This proof is probably wrong. I want to know ...
59 views

Is every computable function the time complexity of some function?

Considering the recent question "Is there an algorithm whose time complexity is between polynomial time and exponential time?", some commenters observed that merely providing a function with ...
49 views

Randomized Algorithm Log-Space Exp-Time

I'm looking for an example of a randomized algorithm that halts with probability 1 (halts almost surely), uses only logarithmic space (worst case) and whose expected run time is not polynomial in the ...
26 views

what should we add to a 2-3 tree to be able to find a value with this time complexity?

I've got this question that asks me to make changes to the 2-3 trees that would make it possible to do a find(x) function that would find x with O(log(rank(x))) . **rank(x) is x's index in a sorted ...
3k views

Problems that are polynomially "hard" to compute but "easy" to verify

In the (unlikely) event that $P=NP$ with a constructive proof of a polynomial time algorithm that solves 3SAT, obviously things will be very different. However, practically, it could happen that the ...
80 views

Check Welzl's algorithm time complexity

From the wiki this is the algorithm and we know that final complexity is O(n) but how we reached to this , is my problem : ...
32 views

What would be the conseuqences of BQP = NEXPTIME?

On wikipedia it says that $BQP ⊆ EXP$. However it is not known if $BQP \subset EXP$ Also I've seen that $PSPACE$ could contain $NEXP$ and does contain $BQP$. For this were assuming the incredibly ...
34 views

What can I say about complexity of this optimisation problem?

I have a set of parameters $\{\alpha_s\}$, and I have $u$ functions of the form $w_i(\{\alpha_s\}) = \prod\alpha_s^{c^{i}_s}$ for some known values of $c^{i}_s$. Similarly, I have $b$ functions of ...
3k views

Is there an algorithm whose time complexity is between polynomial time and exponential time？

We often hear about some algorithms' running time that is polynomial, and some algorithms' running time that is exponential. But is there an algorithm whose time complexity is between polynomial time ...
35 views

Algorithm for the specific problem

A problem : Given a string of number in base $10$ we want an algorithm to calculate the number of numbers, where we replace (only) a single digit to produce a number so that that number is divisible ...
37 views