# 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
10 views

### Proof that DFS order is P-complete

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 ...
25 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 vote
35 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 ...
50 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\}^*$ ...
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: ...
1 vote
42 views

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

Suppose I have this c++ code: ...
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 ...
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 vote
56 views

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 ...
88 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 ...
93 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 ...