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,691 questions
0
votes
0
answers
15
views
What does weaker term mean in the definition of BigO
I am reading Computer Science Distilled book and at 40th page there is a line.
A function with fastest-growing term is $2^n$ or weaker is $O(2^n)$
What does weaker mean here? All, I know it is ...
- 208
0
votes
0
answers
37
views
Why $TIME(2^{n^k})\nsubseteq NTIME(n^k)$?
There is a theorem that said for every nondeterministic Turing machine that runs in $O(n^k)$ there is an equivalent deterministic Turing machine that runs in $O(2^{n^k})$.
From this theorem, I ...
- 191
1
vote
1
answer
84
views
Does log(log(n)) grow asymptotically slower than log(n) / log(log(n))?
I'm trying to understand the asymptotic growth of relationship between log(log(n)) and log(n) / log(log(n)) as n -> infinity.
Specifically, I want to verify whether this statement is true or false:
...
- 13
0
votes
1
answer
61
views
need to prove that $DSPACE(O(2^n)) \neq EXP$
this question is from my computational complexity HW.
I'm not sure if my solution is correct:
If $DSPACE(O(2^n)) = EXP$, than we can take language $ L \in DTIME(2^{2^n})$ which not in $EXP$ (from the ...
0
votes
2
answers
74
views
Must an algorithm terminate to be in NPTIME?
I recently completed a coursework on PRIMES and time complexity, and I got marked down for something which I think I got right, I wanted to ask here to make sure. Here is the problem and I will talk ...
- 1
0
votes
1
answer
29
views
What is the time complexity of determine_build_order function below?
Problem statement: Find out the order in which projects should be build such that dependencies are built first. Dependencies are represented using a list of pairs of projects, where the second project ...
- 15
0
votes
2
answers
75
views
Linear time approximate multiplication
I was searching for the following simple thing, but to my surprise couldn't find anything online.
Is there a linear time approximation algorithm for multiplication or for division. Meaning,
Given I=$[...
- 103
0
votes
1
answer
28
views
Is $\operatorname{ECLIQUE}$ in $\Pi_2^p$?
I was watching this lecture on the Polynomial hierarchy and one of the presented examples was the language \begin{equation*}
\operatorname{ECLIQUE} = \{ \langle G, k \rangle \; : \; G \text{ is a ...
- 85
0
votes
0
answers
7
views
Is there a name for the complexity class for an oracle for matrix elements of arbitrary polynomial-size unitary circuits?
Suppose you had an oracle that could efficiently compute matrix elements (in the computational basis) $\langle x | C | y \rangle$ for arbitrary polynomial-size circuits $C$. Is there a name for the ...
- 1,146
0
votes
0
answers
51
views
Are there any nice examples of problems in E / NE?
Let $E = DTIME(2^{O(n)})$ and $NE = NTIME(2^{O(n)})$ be the deterministic/nondeterministic complexity classes of problems decidable in exponential time with linear exponent.
There are many examples of ...
0
votes
0
answers
27
views
Characterize the following code segment as tightly as can be inferred using Big-O
I am having an argument about what is the complexity that most tightly fits the following code:
‘’’while (n < 1000000)
n = n*2;’’’
I argue that it is O(log n). The worst case, to me, is if n were a ...
1
vote
0
answers
41
views
Polynomial time approximation on a similar problem to Densest-k-Subgraph
Given a graph $G$ with $n$ vertices. Each vertex has a weight $w_i$. For any subgraph $H$, define a function for each vertex of $H$, $f(v_i)$, to be the average of the weight of $v_i$ and all weights ...
- 111
0
votes
0
answers
48
views
Time complexity of Reconstruct Itinerary
This is a question that almost all resources I encountered, leetcode editorial and such, claim a time complexity of $O(E^d)$; and in the comment sections of almost all of them, people, like myself, ...
- 143
1
vote
1
answer
36
views
Types of Time Inconstructible Functions
So Wikipedia gives me notions of time and space constructibility and as far as I can tell, the two general definitions used are:
Functions $f: \mathbb{N} \to \mathbb{N}$ such that for all $n \geq n_0 \...
- 1,647
-1
votes
1
answer
54
views
Is this an algorithm that is theoretically polynomial, but practically exponential?
To solve a problem I have an algorithm $T(n)$ where,
the input of $n$ variables is transformed into $n$ numbers of size $>2^n!$,
then the algorithm requires $k.n^4$ arithmetic operations, where $k$...
- 23
0
votes
2
answers
53
views
Complexity of a naive implementation for selecting top largest $k$ values from an array
I came up with the following algorithm to select top (largest) $k$ values in an array arr containing $n$ comparable values ($k \le n$):
Initialize an empty array <...
0
votes
1
answer
25
views
Time Complexity of Backtracking solution to Leetcode 473. Matchsticks to Square
The following is a Leetcode problem: 473. Matchsticks to Square (https://leetcode.com/problems/matchsticks-to-square/description/)
Problem Statement
You have an array, matchsticks, of size n, with ...
- 1
1
vote
1
answer
48
views
How to separate $TIME(n)$ and $L$?
I'm trying to prove that $TIME(n)\neq L$ by padding technique, yet it has a trouble:
Assume that $TIME(n)= L$, let $A\in TIME(n^2)\backslash TIME(n)$ so $A\notin L$. Let $A_{pad}=\{x01^{|x|^2-|x|-1}|x\...
- 511
1
vote
1
answer
61
views
Is Exponentiation in $FP$?
I am seeing conflicting answers on this question and I could really use some clarification on it. Constructing an algorithm which computes $f[a,b]=a^b$ can be done naively through repeated ...
- 11
3
votes
3
answers
120
views
Can the time complexity of verifying a solution ever be greater than the complexity of the solution
I can not find an example problem space where the complexity (time) of verifying the solution is greater than that of solving the problem.
But I was hoping there would be a formal proof of this out ...
- 133
0
votes
1
answer
71
views
Can top down approach and bottom up approach to a problem have different theoretical time complexities?
I am NOT talking about the speed or time it takes in practice to compute the solution of a problem using top down or bottom up approach. By top down I mean a memoization based approach and by bottom ...
- 1
-1
votes
2
answers
32
views
Explaination of the following time complexity
Recently I dealt a question which is as follows
{$\ldots$
$$partialSum += i* i*i $$ # time complexity is 4n.
}
How can we get this and why is the time complexity not $n+n^3$. We should get $n$ for the ...
- 119
0
votes
1
answer
39
views
Algorithm Analysis Help
I would like help understanding this slide from my class, especially the inner loop part. I do not understand how he is getting at n - (n - 1 - 1) = 2
I do understand that when j = n - 1 we get n - (n ...
0
votes
1
answer
38
views
Complexity of Scheduling n Tasks on m Machines with Identical Execution Times, Dependencies, and Time Lags
This is a scheduling problem with $n$ tasks across $m$ machines. Tasks have dependencies (DAG) and can be divided into two types: A) need resources $R$ and have an identical execution time. B) do not ...
- 1
1
vote
2
answers
63
views
UNIQUE-PATH in P assuming LPATH is in P
We define the following languages:
LPATH = {<G, a, b, k>|G is an undirected graph that contains a simple path of length at least k from a to b}.
UNIQUE-PATH = {<G, a, b>| G is an ...
- 141
1
vote
1
answer
221
views
Which class is the language MAX-CLIQUE in?
We define $$ֿ\text{Max-Clique} = \{\langle G, k\rangle: \text{$G$ is an undirected graph, and the largest clique of $G$ has exactly $k$ vertices}\}$$
Is this language in $\text{NP}$ or in $\text{coNP}$...
- 141
0
votes
1
answer
28
views
P=NP iff for any two non-trivial languages A, B in coNP, A≤pB and B≤pA
Prove: $\text{P} = \text{NP}$ iff for any two non-trivial languages $A$ and $B$ in $\text{coNP}$, it holds that $A \leq_p B$ and $B \leq_p A$.
The part of assuming the reductions and proving $\text{P}=...
- 141
1
vote
1
answer
97
views
Why does problem F belong to PSPACE?
In the following graph, each node represents a computational problem. An arrow like A -> F indicates that there is a polynomial time Karp reduction from A to F. Observe that there could be more ...
- 13
1
vote
2
answers
59
views
prove AP-SUM is NP-complete
EDIT: I had a translation error. Instead of "unuary", it's binary.
AP-SUM is the language defined in the following way:
A word in the language AP-SUM is a pair <S, t>,
so that S is a ...
- 141
1
vote
1
answer
22
views
Complete language in P∪{C,D}
given: C is a NP-coNP language, D is a coNP-NP language and P is the known time-complexity class.
assumption: NP ≠ coNP.
I need to determine if exists a language B, such that:
a. B ∈ P∪{C, D}.
b. for ...
- 141
0
votes
1
answer
33
views
Unusual language in NP
Under the assumptions $\text{NP} \neq \text{coNP}$ and $\text{P}\neq\text{NP}\cap \text{coNP}$, we need to prove that
there is a language $L$ that satisfies the following:
$L\notin \text{P}$.
$L\in \...
- 141
2
votes
3
answers
152
views
How to simplify $O(\log (n!))$?
I have a problem with this time complexity: $\log (n!)+\frac{5}{2}n\log\log n$. I'm not sure how to deal with the $n!$ term. I know from calculus class that the sequence $n!$ is bigger than any ...
- 31
2
votes
2
answers
238
views
Solving the "Reverse" Assignment Problem with an Added Constraint?
Note: This is a continuation of my previous question, found here
As written, my previous question was too unconstrained: @BaderAbuRadi showed that depending on the $C$ chosen, there can be multiple ...
- 55
2
votes
2
answers
203
views
Solving the "reverse" Assignment Problem?
According to Wikipedia, the assignment problem can be formally defined as:
Given two sets, A and T, together with a weight function $C : A \times T \to R$. Find a bijection $f : A \to T$ such that ...
- 55
0
votes
1
answer
50
views
Lower bounds of sieves for factorization
Among factoring algorithms, both the Quadratic Sieve and the Number Field Sieve use sieves to find smooth (pairs of) values, in order to obtain congruent squares $\bmod n$, the number to be factored. ...
- 1,000
0
votes
1
answer
47
views
showing NP completeness for XS
the XS problem:
Input: n final sets and a number k (final sets - finite set of numbers, and k's value can be at most n).
Question: Are there k sets in the n final ones that are not pairwise disjoint?
...
- 141
1
vote
1
answer
54
views
is 3-SAT ∈ NTIME(n^3)?
I'm struggling to understand the time complexity of 3-SAT using a non-deterministic Turing machine, as well as the relationship between NTIME and DTIME
For example, let's say we have 2 literals. My ...
- 13
3
votes
1
answer
85
views
Prove that $n \log n$ is a time-constructible function
I am reading [1]. On page 16 of [1], the authors wrote:
A function $T: \mathbb{N} \rightarrow \mathbb{N}$ is time constructible if $T(n) \geq n$ and there is a TM $M$ that computes the function $x \...
- 243
0
votes
0
answers
80
views
Proof of O(m log* n) time complexity of Union-Find - Is wikipedia proof wrong?
On wikipedia (https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Proof_of_O(m_log*_n)_time_complexity_of_Union-Find), they prove that the amortized time for any m Find or Union operations on a ...
0
votes
1
answer
51
views
Relationship between $\omega$ and o
I have for every constant $c$ (no matter how large) and for every $\epsilon >0$(no matter how small), how can I show that
$$n.e^{\sqrt{\log n}}=\omega(n\log^c n)\\
n.e^{\sqrt{\log n}}=o(n^{1+\...
user172436
1
vote
0
answers
30
views
DLOGTIME sequential access (uniformity conditions for circuits)
Consider the direct connection language of a circuit family, consisting of tuples (a,p,b,y) where
a is a gate number
p a binary string is an encoding for a predecessor or type
b is a gate type or ...
- 193
2
votes
1
answer
75
views
Algorithms that are better than brute force
Is there a mathematical explanation for why problems have algorithms that are better than brute force? It feels like we have to take advantage of some type of order that could help us identify ...
- 29
4
votes
3
answers
588
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 ...
- 230
6
votes
0
answers
112
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 ...
- 61
3
votes
1
answer
64
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 ...
- 31
1
vote
1
answer
51
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
24
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
111
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
251
views
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 ...
- 243
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