# 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,574 questions
Filter by
Sorted by
Tagged with
19 views

### Proof that DFS order is P-complete [closed]

Suppose we are given an oriented graph G with a selected number of nodes s, where for each node some particular ordering of edges leading from it is specified. If we run a depth-first search algorithm ...
26 views

### What is the largest "allowed" seed for a PRNG to not give any extra power to a deterministic machine?

Suppose a polynomial time machine that has an access to a polynomially long string of bits independent on the input. On average, it's impossible to compress this string to a subpolynomially long ...
• 1,429
1 vote
36 views

### How do i make a 2d array as same as i possibly can with another one?

Say i have an 2d array A of nxn size, int values already given for each item.these values can be the same or different. There's gonna be another nxn array B being input. I can only interchange one row ...
53 views

### Necklace Alignment Problem

We are given two cyclic $\{0,1\}$ strings $X$ and $Y$ with both length $n$, containing $k$ 0s and $n-k$ 1s. Suppose positions of 1 in $X$ are $x_0,\dots,x_{k-1}$, for $Y$ are $y_0,\dots,y_{k-1}$. We ...
29 views

### What's the Time Complexity and total no of iterations?

for a=1 to m means for(a=1;a<=m;a++) for i=1 to n for j=i to n c= c+1; The total no of iterations is O(n^2) ...
23 views

### $NL$ Leaf languages and $PSPACE$

I am reading Papadimitriou's Computational Complexity and got stuck on part d) of the following exercise (pg. 505) 20.2.14 A panorama of complexity classes. ... A language $L \subseteq \{0, 1\}^*$ ...
• 3
28 views

### Time complexity of algorithm involving function calls

Me again. This time I have a more general question. Suppose I have the following code snippet: ...
• 167
1 vote
44 views

### Time complexity of algorithm with three loops and if statement

Suppose I have this c++ code: ...
• 167
19 views

### Why is $DSPACE(\log^2n)\subseteq DTIME(n^{\log n})$?

I am having trouble with the statement that $DSPACE(\log^2n)\subseteq DTIME(n^{\log n})$ holds which is given without argument in the paper The structure and complexity of minimal NFA's over a unary ...
16 views

### Runtime of randomization algorithm to find majority element in an array?

This is for the leetcode problem 169. Majority Element. Given an array of numbers, where there is a guarantee that there is a number that exists in the array greater than floor(n/2), one can find such ...
• 111
21 views

12 views

### FPL class problem into P class problem?

Say I have an FPL class problem with the complexity O(2^k * n). If I limit the problem so that k is a known factor (for example 150). Then the complexity becomes O(2^150 * n). I have learnt that ...
• 1
1 vote
56 views

• 335
1k views

### Is there a faster algorithm than FFT if interested only on the maximum amplitude frequency?

Given an $n$ input array, is there an algorithm that is faster than Fast Fourier Transform if we are only interested in obtaining the maximum amplitude frequency? Looking at the Cooley–Tukey algorithm ...
• 254
89 views

### Time complexity of GPU computing

The time complexity of the matrix product is $O(n^3)$ if calculated normally for each element. If computed on GPU, is it $O(n)$? What I thought: GPU can compute each element of the matrix product in ...
• 3
95 views

### Are integer linear *feasibility* problems NP-hard?

I know that Integer Linear Programming problems are NP-hard. But it seems like this answer is only applicable to Integer Linear optimization problems. It seems like integer linear feasibility problems ...
1 vote
30 views

### Time complexity of a convergent series

I wanted to ask a simple question: Assume I have a function whose time complexity is given by the following function: $T(n)=\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+...+\frac{1}{n^2}$. Would it be ...
27 views

### Time complexity of function

int q(int n) { if (n <= 0) return 0; return 1-q(q(n-1)); } I'm not sure how to approach this. I tried representing the time complexity as a ...
1 vote
54 views

### Are there situations where we can decrease the time complexity of a program by increasing its ordinal complexity?

Are there (interesting) situations where we can decrease the time complexity of a program by increasing its ordinal complexity? For example, is it possible to find a primitive recursive function such ...
• 177