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
0
votes
0
answers
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 ...
0
votes
1
answer
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,417
1
vote
0
answers
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 ...
- 11
0
votes
0
answers
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 ...
- 1
0
votes
1
answer
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)
...
0
votes
1
answer
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
0
votes
2
answers
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
1
answer
42
views
Time complexity of algorithm with three loops and if statement
Suppose I have this c++ code:
...
- 167
0
votes
1
answer
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 ...
- 11
0
votes
0
answers
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
0
votes
1
answer
21
views
Enumerating proper intersections
Let
$U \subset \mathbb{N}$ be a finite universe set;
$B$ be a set of nonempty subsets of $U$ such that $B$ covers all elements in $U$, i.e. $\bigcup_{b \in B} b = U$, and if $b \in B$ then $b \...
0
votes
2
answers
22
views
How to calculate the time complexity if the upper bound is decreasing as well?
For example if the condition is i<=n, and the n is decreasing in the loops, how can i calculate the time complexity?
Lets say we have nested loops like below:
...
0
votes
2
answers
42
views
Why does lexer has O(n) time complexity?
According to my CS knowledge so far, a lexer uses DFA(which takes linear time) for 'each' token type to find the next token, so in the worst case, it should try 'all possible' token types of a ...
3
votes
0
answers
126
views
Recover unknown vector through shifted argmax queries
I am interested in finding an efficient algorithm for the following problem:
Let $x \in [0,1]^n$ be some vector, with $x_n = 1$.
We want to recover $x$, solely by asking queries of the form $\texttt{...
0
votes
0
answers
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
1
answer
56
views
Show if $f(n)$ has polynomial growth and $g(n)=\Theta(f(n))$, then $g(n)$ also has polynomial growth
As stated in the question title, if $f(n)$ has polynomial growth and $g(n)=\Theta(f(n))$, then how can we show $g(n)$ also has polynomial growth?
$g(n)=\Theta(f(n))$ gives us $0\leq c_1f(n)\leq g(n)\...
- 151
0
votes
1
answer
37
views
Solving Recurrence Relations with induction
We got the following tasks in our Higher Algorithm class, to repeat our proof techniques from class:
Find asymptotic upper bounds (as sharp as possible) for $T(n)$ in each of the following cases,
...
15
votes
4
answers
2k
views
Is there a known polynomial time complexity problem with bad constants?
As you know, big O notation hides all constants. For instance, both runtimes $T_1=n$ and $T_2=10^{10}n$ are considered to be linear ($\mathcal{O(n)}$).
Is there an iconic problem whose best known ...
0
votes
1
answer
34
views
How are pointers modeled on bit-based computer models?
Why bit-based computer models?
The perhaps most commonly used computer model is a random access machine that can store natural (or even real) numbers in infinitely many cells indexed by natural ...
- 103
1
vote
1
answer
39
views
Proving lower bound by proving not little o
I have been reading these distributed computing notes. In some of the proofs, for proving lower bound of $\Omega(f(n))$, we prove that no algorithm which solves the problem in $o(f(n))$ exists.
I can'...
- 11
1
vote
1
answer
45
views
Converting encrypted messages to unencrypted results of an equally hard to reverse function
If we have some function, $f$ with an exponentially sized domain, mapping the set $\{0, 1\}^N$ to $\{0, 1\}$, could we do something like this:
For ease, let's say $E(x) = x^e (\text{mod} \; n)$. This ...
- 55
0
votes
0
answers
26
views
If $NP \ne coNP$, $L_1, L_2 \in NP$, then is it necessary for $\bar{L_1} \cap L_2 \in NP$ and checking the proof of $P \ne NP$
I am a beginner in the computer science track.
I have some problems with the following problems
Problem 1: Assume that $NP \ne coNP$. If $L_1, L_2 \in NP$, is $\bar{L_1} \cap L_2$ necessarily in $coNP$...
- 1
2
votes
1
answer
35
views
Time complexity of an uneven binary search
I have a concept binary search which doesn't split at the midpoint of a list, but at a ratio of 1:2.
If we abstract the search function time complexity into $T(n)$ then the function can recurse into ...
- 33
0
votes
2
answers
45
views
Prove $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})=\Theta(n\log^2{n})$ using induction
Please first take a brief look at my previous question. Here I want to do something similar but for $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})$. I know the answer is $T(n)=\Theta(n\log^2{n})$ and I want ...
- 151
0
votes
1
answer
34
views
find $f(n)$ for recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})=\Theta(f(n))$
We have recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})$ and
assume $T(1)$ is a constant. Find asymptotically tight bounds
$\Theta(f(n))$ for $T(n)$.
There's something that confuses me. We ...
- 151
0
votes
1
answer
23
views
Time complexity and content free evaluation
I am having trouble answering the question below:
"Explain why the statement, “The running time of algorithm A is at least O(n^2)”, is content-free."
The statement apparently does not give ...
- 3
0
votes
1
answer
54
views
Find time complexity of $T(n)=3T(n-2)+O(n)$
I try to find the time complexity of following recurrence relation:
$$T(n) = 3T(n-2) + O(n)$$
After subtitution,I get:
$$T(n)=3^{\frac{n}{2}}T(0)+\sum_{i=0}^{\frac{n}{2}-1}3^iO(n-2i)$$
I wonder if the ...
- 3
1
vote
2
answers
71
views
Time complexity of using BFS to find shortest path within k stops
I'm referencing this Leetcode question: https://leetcode.com/problems/cheapest-flights-within-k-stops/solution/, which asks you to find the length of the shortest path from source to dest using less ...
- 11
1
vote
2
answers
141
views
Prove $T(n)=10T(\frac{n}{3})+n\sqrt{n}=\Theta(n^{\lg_3{10}})$ using induction
We have this recurrence: $$T(n)=10T(\frac{n}{3})+n\sqrt{n}.$$
We can solve it using Master Theorem and say it is
$\Theta(n^{\log_3{10}})$. I want to prove it using induction but I don't
know the ...
- 151
1
vote
0
answers
12
views
Computation of composition of analytic functions [closed]
There are several algorithms available for computing the approximate values of functions. These can involve methods like the arithmetic-geometric mean or the Taylor series. Given a set of analytic ...
- 11
1
vote
1
answer
132
views
Sorting O(log n) elements in O(n) time
I am presented with the following problem: In an array of $n$ sorted numbers and $f(n)$ unsorted numbers where $f(n)=O(\log n)$, find an algorithm to sort the entire array in $O(n)$ time.
What I am ...
- 11
0
votes
1
answer
31
views
time complexity of loops
what is the time complexity of:
for (i = 1; i <= n; i = 2*i)
for (j = 0; j < i; j++)
sum++;
?
I thought it is O(nlogn) since the otter loop ...
0
votes
0
answers
18
views
Time complexity summations
How to calculate the time complexity of a algorithm which contains while loops or if statements using summations? I only know how they work with the for loops. And I'm guessing the if loop are ...
- 1
2
votes
1
answer
107
views
What is the time complexity of this algorithm of finding all prime numbers?
I came up with this algorithm for finding all prime numbers from 1 to n. This algorithm could already exist, if it does I don't know what it is called.
...
- 31
0
votes
0
answers
34
views
Minimum spanning tree using BFS
In finding a minimum spanning tree, if we use a BFS and at any node instead of deleting the edge to a repeated node, we can find the most expensive node in that cycle instead and delete it.
In such a ...
1
vote
2
answers
38
views
Finding growth rate of T(n) of a code segment
I am presented with the following code segment and asked to find the growth rate, which can be done by finding the number of times the variable sum is incremented:
...
- 11
0
votes
1
answer
75
views
T(n) = T(n-1) + T(n-1) vs T(n) = 2*T(n-1)
If I have 2 version of code
1.)
def T(n):
if n == 0:
return 1
return T(n-1)+T(n-1)
2.)
...
- 5
1
vote
0
answers
73
views
Why in Edmonds Karp or Ford Fulkerson Algorithm the time complexity of BFS or DFS respectively is O(E) rather than O(V+E)?
For these algorithms, the time complexity of BFS and DFS is O(E).
I have gone through many websites and even the algorithm books, but I never got a clear idea of why it is O(E). It just says it's O(E) ...
- 11
0
votes
1
answer
67
views
The math behind the time complexity of Heap Insertion
Insertion into a heap is an O(logn) operation. Insertion of n elements into a heap one by one is summarised as O(n * logn). I wonder about the math behind this, because I could not reach to the same ...
- 105
1
vote
0
answers
63
views
Is NP a subring of the 2-adic integers?
Let me take the set $A = \{1, 2\}$ as the alphabet. By the bijective binary numeral system, $A^*$ has one-to-one correspondence to the set of nonnegative integers $\mathbb{N}$. As such, each language $...
- 335
5
votes
1
answer
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
0
votes
3
answers
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 ...
- 3
2
votes
1
answer
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 ...
- 25
1
vote
1
answer
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 ...
- 135
0
votes
2
answers
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 ...
- 135
1
vote
1
answer
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
5
votes
5
answers
3k
views
Time Complexity of Linear Search vs Brute Force
I am currently watching the FreeCodeCamp Algorithms and Data Structures Tutorial. In the explanation for exponential time complexity, they explain that using a brute force attack on a combination lock ...
1
vote
1
answer
59
views
Validity of time complexity analysis
Given recurrence equation :
$T(N) = T(N-1) + T(N-2) + N$
Given base case
$ T(1) = -3$
So I rewrote the equation as
$ T(n)+ n - T(1) = T(n-1)+ (n-1) - T(1) + T(n-2)+(n-2)-T(1)$
Substituting $ V(n) = T(...
- 113
0
votes
1
answer
22
views
How to estimate T(2N) from T(N) of mergesort?
This question is from Exercise 1.7 in the book An Introduction to the Analysis of Algorithms by Robert Sedgewick and Kevin Wayne.
Assume that the running time of mergesort is $cN\lg{N}+ dN$, where $c$...
- 101
0
votes
0
answers
27
views
Recurrence for C(N+1) - C(N) of mergesort
I am reading "An Introduction to the Analysis of Algorithms" by Robert Sedgewick and Kevin Wayne. In this book, Exercise 1.4 asks to develop a recurrence for $C_{N+1} - C_{N}$ and use it to ...
- 101