# 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].

1,487 questions
Filter by
Sorted by
Tagged with
8 views

### Summation of asymptotic notation

How can we solve summation of asymptotic notations like given below: Summation (BigO(n)) over k for 0 < k < n.
5 views

### time complexity turing machine equal to “n + 1”

I have not clear why the time complexity is n+1 and not n+2. Consider a TM with a single tape and alphabet {0,1} and the string | * | 0 | 1 | 1 | 0 | 1 | 0 | * | ...
486 views

### Are there any proofs of exponnential lower bound time complexity

I'm trying to understand what are the techniques to prove an exponential time lower bound. For some problems, we can prove that the size of the output is exponential is the size of the input, thus it ...
40 views

### Why is finding the closest pair of points by brute force search O(n^2)?

If I have n points A, B, C, D it seems like finding the closest pair via brute force search would go like: Compare A to every item (n-1) Compare B to every item (...
21 views

### Determine if an NFA accepts infinite language in polynomial time

Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite. (Note that converting NFA to DFA is exponential time). For any DFA,...
33 views

### Time Complexity: Big-O

What is the time complexity of this loop? k=1 for(j=0;j<=n;j+=k) k++; Is it $O(n)$ as we are increasing $j$ linearly?
25 views

### Conditions under which the 3-partition problem is not strongly NP-complete?

I'm a bit confused about the 3-partition problem. More specifically I'm confused about this from the Wikipedia article: Let B denote the (desired) sum of each subset Si, or equivalently, let the ...
45 views

### Finding minimum in PRAM model

Show that the minimum of $n$ elements stored in an array can be found in a time in $O(\log(n))$ using $O(n/\log(n))$ processors assuming an EREW-PRAM machine is given.
24 views

### Upper bound for runtime complexity of LOOP programs

Recently I learned about LOOP programs, which always terminate and have the same computational power as primitive recursive functions. Furthermore primitve recursive functions can (as far as I ...
90 views
+100

### Time Complexity for Nearest Neighbor Searches in kd-trees

Nearest neighbor searches in kd-trees run in logarithmic time, as shown by Friedman et al. However, I have some difficulty to fully understand the proof. In order to calculate the average number of ...
26 views

### sequence of insert and delete operation in (2,3)-tree

I need help by understanding a theorem and its proof from a script. It says "There is a sequence of $n$ insert and delete operations in a (2,3)-tree that require $\Omega ($n log n$)$ many split and ...
21 views

23 views

### Check the Complexity time of Power method

Hi i have write a function in Matlab to calculate the power method and i wont to find the time complexity. ...
20 views

### Complexity of finding an alternating Hamiltonian (x,y)-path in edge bicolored complete graphs

Let $G$ be a simple complete graph with an edge-2-coloring. An alternating Hamilton (x,y)-path is a Hamiltonian path which starts at vertex $x$ and ends at vertex $y$ such that the colors of its ...
30 views

### MaxClique is DP-hard

I want to show that MAX−CLIQUE={(G,k)|the largest clique of G is of size exactly k} is DP-complete The idea is reduce MAX-CLIQUE to C={(G1,k1,G2,k2) | G1 has a k1-clique and G2 does not ...
115 views

### Solving $T(n) = T(n/2) + T (n/3) + n$ with recurrence tree

I am trying to solve the following recurrence relation: $$T(n) = T(n/2) + T (n/3) + n$$ $$T(1) = Θ(1)$$ I guess that the time complexity is $T(n)=Θ(n)$ since $\frac{n}{2} + \frac{n}{3} < n$ I ...
36 views

### Complexity of Hamilton path in directed complete bipartite graphs

Finding a Hamiltonian path in a directed bipartite graph is NP-complete. Problem 1 What is the complexity of the problem if we insist that the underlying graph of the digraph be complete ...
41 views

### What is the time complexity of this nested loop code?

In this loop $j$ is dependent on $i$, and $j$ is executing like $n/2$, $n/2-1$, $n/2-2$, ... So does this sum up to $O(n\log n)$?
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 ...
52 views

### Time Complexity of the below code? [duplicate]

here is a nested loop where all the variable are integers.This is another question to the thread. I understood the solution part , but stuck in the time-complexity part. What is the time complexity ...
50 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. ...
26 views

### Worst Case running time of the Minimum Vertex Cover Approximation algorithm

Considering this factor $2$ minimum vertex cover approximation algorithm : Repeat while there is an edge: Arbitrarily pick an uncovered edge $e=(u,v)$ and add $u$ and $v$ to the solution. ...
53 views

### How to mathematically prove that a relation T(n)=T($\sqrt{n}$)+c is O(log(log(n))?

following question, I understood the intuition behind how cutting down the size of input by square root on each iteration leads to O(log(log(n))) complexity. I tried to derive it on paper. Let T(n) =...
123 views

### Minimum descending stacks

Assume a randomly ruffled pack of n cards with numbers from 1 to n. Each time we pick the top card from the pack (while there are still cards) and we put them according to the following rules: The ...
59 views

37 views

### Are chaotic systems computable in polynomial time

Suppose the parameters/inputs of the computation include the time at which the configuration of a particular deterministic chaotic system needs to be computed. Say, for instance, as input we have a ...
21 views

### Highest safe rung problem?

Highest Safe rung problem : There are many rungs on a ladder in increasing order of height. A bottle is thrown from a rung, and depending on the height of the rung, the bottle may break or may not (...
39 views

### Do problems that have unary encodings automatically become unary languages?

This problem has confused me a lot, can any of you help me out. Thank you.
39 views

### Why does this triple loop code have a running time of 1.5lnN * N^2

Hi all, I'm currently going through the Princeton Algorithms course on coursera, and I'm having trouble understanding the answer to this quiz. I think I understand where the $\frac{1}{2} N^2$ term ...
The $3-SAT$ problem is known to be NP-complete problem. Which means that (as far as I understand), unless $P \neq NP$, for every algorithm $A$ which decides $3-SAT$, $A$ runs in super polynomial time (...