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
0
votes
1answer
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. ...
0
votes
0answers
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. ...
2
votes
0answers
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 ...
2
votes
1answer
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$. ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
2answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ?
1
vote
2answers
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 ...
0
votes
1answer
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. ...
0
votes
0answers
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, ...
0
votes
1answer
62 views

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

Generalized chess is EXPTIME complete[1]. Generalized chess is also PSPACE complete[2]. Therefore $EXPTIME = PSPACE$. This implies that $P \neq PSPACE$ This proof is probably wrong. I want to know ...
3
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
30
votes
1answer
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 ...
1
vote
1answer
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 : ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
11
votes
4answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
37 views

Algorithm for finding a specific ordering of nodes in a graph $G=(V, E)$ in $O(|V|+|E|)$ time

I have an undirected graph $G=(V,E)$ and I want to find an ordering of $V$, $\pi=(v_1, v_2, ..., v_n)$, such that for each $1 \leq i \leq n$, $v_i$ is of minimum degree in the subgraph $G_i = [\{v_1, ....
3
votes
3answers
109 views

What is the runtime/time complexity of Coq’s (Dependent) Type Inference?

I remember learning in a class that type inference is decidable but usually takes a long time (e.g. type inference in OCaml is EXPTIME). I was wondering, since Coq allows programs/values themselves to ...
0
votes
1answer
17 views

Efficiently Taking the Sums of all Pairs of Elements from a Set

I have a set of numbers and I want to find the sums of all possible pairs of elements. With the set $\{1, 2, 3\}$ for example, I would want $\{1+2, 1+3, 2+3\}$ as my answer. I could do that in n^2 ...
1
vote
0answers
32 views

Maximize the sum of weights of covered intervals

Suppose we are given $n$ open intervals $(a_1, b_1), \dots, (a_n, b_n)$, with interval $i$ being assigned a weight $w_i$ for all $i$. We are given an integer $k<n$, and we are allowed to choose $k$ ...
0
votes
0answers
20 views

Upper bound time complexity

I have an algorithm that for $n$ iterations performs some insertions into a set and priority queue. I know that in the last iteration (the case where time complexity is always worst), the time ...
0
votes
1answer
28 views

What are some examples of problems in R but not in PR?

Also are there any R complete problems? These would be the hardest decidable problems to my knowledge. Sorry if this isn't specific enough.
0
votes
1answer
32 views

If the time hierarchy theorem holds relative to every oracle, what about a halting(RE) oracle?

I may be misunderstanding this. But the halting problem ∈ RE-complete. P ⊂ RE EXP ⊂ RE. therefore EXP^RE = P^RE = RE(my logic might be(is probably)) wrong here, please edit it if it is to be right) ...
0
votes
0answers
32 views

Is a polynomial function that is O(e^x) possible? [duplicate]

Are there any polynomial functions that are $O(e^x)$? Is this possible?
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 ...
0
votes
1answer
33 views

Solving a recurrence relation with two variables

I have this function which traverses each node of a left child-right sibling binary tree once and I want to solve the recurrence relation of the function. First of all I think the relation looks like ...
2
votes
1answer
34 views

find vertex cover of size at most 30 of a graph

This is a question from an exam I got wrong. Given an undirected graph $G$. Consider the decision problem of finding if there exists a vertex cover of size at most 30. Can we find a polynomial time ...
0
votes
2answers
70 views

Examples of time complexity $O(n^k)$

I am looking for some algorithms(examples) whose time complexity is given by $O(n^k)$. It could be any problems that you have come across. Please reply. Thanks!
2
votes
1answer
11 views

Question on worst-to-average-case reductions

Consider two decision problems A and B. We know that A reduces to B in polynomial time --- if we could solve B, we have a procedure to solve A. Now, let's say it is known that the worst case instances ...
1
vote
0answers
19 views

N dimensional point, storage and access

Consider the case where you have 3-dimensional space. You want to know whether at a given point (x,y,z) in space, does anything exist(just like checking if in a 3D array at (x,y,z) is there a 1 or 0). ...
2
votes
1answer
35 views

Union of multiple overlapping sets efficiently?

I have $n$ sets, each of which overlaps heavily with the other sets, and I want the union of all of them. The obvious solution is to take the union of each set, one by one, which results in $O(n^2)$ ...
1
vote
0answers
43 views

Has term pseudo-logarithmic standard meaning?

Whenever an algorithm has polynomial complexity, but exponential over the encoding of the input, it is said to be pseudo-polynomial. What about logarithmic complexity? Wouldn't be wrong to refer to ...
0
votes
1answer
27 views

Is integer multicommodity flow problem is NP-hard?

As Wikipedia states the time complexity of Integer Linear programming(ILP) is NP-hard, so this means integer multicommodity flow problem is also NP-hard?
1
vote
0answers
14 views

Design a two-tape deterministic Turing machine M that recognizes the language L3= {x#(0^k) #y : x, y ∈ {0, 1}* , x = y ∧ |x| = k}

I'm having a hard time trying to write a two tape Turing machine I wanted to first think Oh all I'd have to do is scan from left-to-right till I find the strings that matches the accepted strings) ...
0
votes
0answers
26 views

Time complexity ordering a vector of size $n$ vs $m$ vectors of size $m_i$ such that $\sum_{i}{m_i}=n$

If one has a vector of size $n$, one can sort it in $O(n \log{n})$. If one has $m$ vectors of size $m_i$ each, such that $\sum_{i}{m_i}=n$, what's the total time complexity to sort all of them? I ...
0
votes
2answers
70 views

Is log^2 (n) ∈ O(n) true?

I'm new to algorithm, and I am already overwhelmed with the term ∈ I really could use some good explanation.
3
votes
1answer
85 views

How is the time complexity of a non-deterministic Turing machine defined?

I read different things online about this: In Sipser, p. 283. The time-complexity of a NTM is defined as the maximum number of steps it uses on any branch on any input of length n. So this is only ...
0
votes
1answer
17 views

A high-level call-by-reference question

First, let $H$ be a graph represented as an array of adjacency lists say. Next, let FindDegree$(H,y)$ be a standard subroutine that takes $H$ and a vertex $y$ in $H$ as input, and that returns the ...
0
votes
1answer
31 views

Complexity of insertion into a linked list, single vs double

At https://www.javatpoint.com/singly-linked-list-vs-doubly-linked-list, it says: In a singly linked list, the time complexity for inserting and deleting an element from the list is O(n). And: In a ...
2
votes
0answers
17 views

UCYCLE in LOGSPACE and linear time

Consider UCYCLE, the problem of recognizing undirected graphs containing a cycle. On the one hand, it's in LOGSPACE, see this stackexchange thread: start at every vertex $v$ a DFS and check whether it ...
3
votes
2answers
60 views

All possible sum of each array combination

Is there a name for this algorithm? I have an array {1,2,3} and all my possible sums are {1},{2},{3},{1+2},{1+3},{2+3}, {1+2+3} = {1},{2},{3},{4},{5},{6} {1,1,2} => {1}, {2}, {3}, {4} I tried to ...
1
vote
1answer
20 views

Solve recurrence where the base case's time complexity is a function of the original input size

I'm trying to analyse the time complexity of the following algorithm for generating the power set: ...

1
2 3 4 5
44