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,657
questions
-1
votes
0
answers
9
views
Sliding Window Subarray Question - TLE
Question:
Given an integer array arr[] of size n. Your task is to count the number of good subarrays of
the given array arr.
Here any subarray arr[l ... r] is considered to be good if it satisfies the ...
4
votes
3
answers
416
views
Accelerating semidecision of halting problem
There is a naive semidecision algorithm for the halting problem: simply simulate the program and see if it halts. Is there an algorithm that is asymptotically faster? More precisely, suppose the naive ...
- 218
4
votes
0
answers
78
views
Polynomial time algorithms for graphs and cycles
For a given undirected graph $G$ , let $ c(G) $ denote the length of the longest cycle in $ G $ (by cycle, we mean a closed path without repetitions). Prove that if there exists a polynomial-time ...
- 41
2
votes
1
answer
53
views
How to prove a problem is EXP hard
Summary of the problem: Given an alternating time turing machine ($M$), a polynomial $p(.)$ and a string ($w$), is it EXPhard to find if $M$ accepts $w$ using not more than $p(|M|+|w|)$ space?
My ...
- 21
1
vote
1
answer
46
views
Relaxed form of the graph isomorphism problem?
Let $G_1=(L_1,R_1,E_1)$ and $G_2=(L_2,R_2,E_2)$ be bipartite directed graphs and let $\lambda:L_1\to L_2$ be a bijection between the $L$ vertex sets of the graphs. If I wanted to determine whether $...
- 255
1
vote
0
answers
22
views
Help required for an example of a restricted 3,3-SAT problem instance?
"Let r,s-SAT denote the class of instances with exactly r variables per clause and at most s occurrences per variable. We prove the 3,4-SAT result to be the strongest possible and show that 3,3-...
- 745
3
votes
2
answers
88
views
Proving that $T(n)=16T\left(\frac{n}{4}\right)+n! \in \Theta(n!)$
I am trying to prove that $T(n)\in\Theta(n!)$ for the following recurrence using the master theorem:
$\qquad T(n) = 16T\left(\frac{n}{4}\right)+ n!$
My attempt
We have that $f(n) = n! \in \Omega(n^{\...
- 133
5
votes
1
answer
167
views
+50
Prove that $n$ is a time-constructible function
I am reading Arora and Barak's book: "Computational Complexity: A Modern Approach". On page 16, the authors wrote:
A function $T: \mathbb{N} \rightarrow \mathbb{N}$ is time constructible if ...
- 237
1
vote
1
answer
18
views
Given that A linear-time reduces to B, what is the solvable relation?
What can you infer from the fact the problem A linear-time reduces to problem B?
If there exists an O(n^3) algorithm for problem B, then there exists an O(n^3) algorithm for problem A
If there exists ...
- 21
2
votes
1
answer
75
views
Why would the existence of a sufficiently strong PRNG prove P=BPP?
The $P$ vs $BPP$ question is often explained as such: if there exists a "strong enough" PRNG, we can use it to derandomize any randomized algorithm.
However, I don't get how this, let's call ...
- 907
3
votes
1
answer
47
views
Is $\text{BPP}$ the largest polynomial-time "tractable" complexity class?
An algorithm is in $\text{BPP}$ if it is a) guaranteed to halt in polynomial time, and b) gives the right answer with some probability $p > 0.5$ independent of the input. $\text{BPP}$ is ...
- 907
2
votes
1
answer
112
views
Deducing upper bound for Boolean Circuit size from well-known algorithms
Given an algorithm A for computing binary function $f$. Assuming that A runs in time $t(n)$, what could we say about the size of the minimal Boolean circuit C that calculates f? I think that it ...
- 231
0
votes
0
answers
19
views
Do I need to display constants in the step count method
I tried looking this up before coming here but I couldn't find any resources. If there is a post that already exists that can explain this please let me know so I can close this one.
I am creating ...
- 11
2
votes
0
answers
26
views
Relative running times of equivalent Turing machines with arbitrary and binary alphabets
The book "Computational Complexity: A modern approach" by Sanjeev Arora and Boaz Barak contains the following claim:
Claim 1.5 For every $f : \{0, 1\}^∗ \to \{0, 1\}$ and time-constructible ...
- 121
1
vote
1
answer
66
views
Why is the time complexity of bidirectional breadth first search still considered O(V + E)?
I understand that if the branching factor of the graph is b and distance of goal vertex from source is d, then the time complexity is O(b^d).
I also understand why that would be O(b^d/2) using ...
- 131