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.

Filter by
Sorted by
Tagged with
1 vote
3 answers
113 views

What is the difference between solving and verifying an algorithm in the context of P, NP, NP-complete, NP-hard

I am struggling to understand the difference between the notions $P, NP, NP-$complete, $NP-$hard. Let's take the example of the $NP-$class. We say that these problems are solved in non-polynomial time,...
0 votes
2 answers
61 views

Why the APPROX-VERTEX-COVER algorithm is O(V+E)?

In the Introduction to Algorithms Book By Thomas H. Cormen, Third Edition, they give an approximation algorithm for the Vertex Cover Problem with 2-approximation ratio: Where G is undirected graph. ...
  • 59
0 votes
0 answers
15 views

Finite complexity meta-algorithm to generate (non-asymptotically) polynomial time shortcuts to EXPTIME problem of arbitrary input size

I might be able to find a polynomial time reduction to an EXPTIME algorithm of finite size, but is it possible for a finite-description-length algorithm to exist that finds polytime shortcuts for any ...
1 vote
0 answers
28 views

Are there EXPTIME-complete problems which are also in IP?

I am wondering if there are known to be any EXPTIME-complete problems (or even just problems in EXPTIME) which are known to also be in IP, so a prover can convince a verifier that an answer to an ...
-3 votes
2 answers
45 views

Iterative solution of recurrence relation $T(n)=4T(\frac{n}{2})+\frac{n^3}{log_2n}$

Please help me to find the Time Complexity of the recurrence relation $T(n)=4T(\frac{n}{2})+\frac{n^3}{log_2n}$ using iterative method.
  • 1
3 votes
1 answer
57 views

Proof sketch of Blum's Speedup Theorem

In his Quantum Computing Since Democritus, Scott Aaronson outlined a proof sketch of Blum's Speedup Theorem which roughly looks like the following. Given an enumeration of Turing Machines $\{M\}_{i \...
  • 31
1 vote
1 answer
37 views

Why is calling an O(n) time algorithm on each node of a tree O(nlogn) time?

Assume we have a balanced binary tree. On each node, we call: ...
0 votes
1 answer
29 views

What are some algorithms with runtimes that involve a \log{n} term with a negative exponent?

Are there any (deterministic or randomized) algorithms that run in time $\operatorname{poly}(n)\log^p{n}$ for $p < 0$? What are some examples?
  • 971
1 vote
1 answer
46 views

Time complexity for finding the number of triangles in a graph

In our class we considered the problem written in the title. The below given time complexities where simply given, but not derived or explained. Therefore I tried myself to derive them, while I using ...
  • 185
1 vote
0 answers
28 views

Time complexity of LP problems

In almost all websites and papers, the complexity of LP problem is given in the number of iterations (such as https://or.stackexchange.com/a/5924). I was wondering if there are any references where ...
0 votes
0 answers
27 views

What will be the Computational Complexity in terms of order O of the operations shown in the following figure

Suppose I have L bits. First, I want to multiply the L bits with L orthogonal codes of length N, and then I want to add all the vectors. So, first, I have to do a scalar multiplication with a vector ...
1 vote
1 answer
68 views

fastest algorithm for rectangular linear assignment problem

I want to optimally assign $m$ jobs equally to $n$ workers, where $m>n$. Assume $m = an$ for some integer $a$, so that each worker must get exactly $a$ jobs. (The rectangular linear assignment ...
  • 90
1 vote
1 answer
121 views

Find the largest segment within a queried range?

We are given $k$ segments $(s_1,e_1),(s_2,e_2),(s_3,e_4),...,(s_k,e_k)$ where $s_i\le e_i$. Now we are given a query interval $[L,R]$ to find the largest segment $(s_i,e_i)$ contained within $[L,R]$. ...
3 votes
2 answers
88 views

Rank in a Convex Combination

Given vectors $A, B \in \mathbb{R}^{n}$, $w \in [0,1]$ and $x \in \mathbb{R}$, let $$ Rank(A,B,w,x)=\sum_{i=1}^{n} \boldsymbol 1 \{w A_{i} +(1-w) B_{i} < x\} $$ denote the number of elements in the ...
0 votes
1 answer
48 views

Complexity of solving two different LP problems

I have one LP problem (LP1) to solve, where a term in a constraint is to be substituted after solving another LP problem (LP2) (with a different variable vector). Suppose I call the dimension of the ...
1 vote
1 answer
47 views

Turing machine read time

Suppose I have a Turing machine that takes as input any string of length $n$, where $n$ is odd, and the Turing machine returns the middle character of the string. What time complexity class is this in?...
1 vote
1 answer
33 views

shortest path increases monotonically => a bound on the length of one iteration of Edmons-Karp is then O(E) ... Convince me this is true

I was reading the proof of time-complexity for the Edmonds-Karp algorithm here (https://brilliant.org/wiki/edmonds-karp-algorithm/). Everything in the first part of the proof (The section ...
3 votes
1 answer
91 views

Given two strings ABC and CBA, find A, B and C

Given two strings ABC and CBA, find A, B and C. Input: abcacab, cabcaab Output: ab, ca, cab The time complexity of brute force is O(n^3). Are there any better algorithms to solve this problem? Thanks!
-2 votes
1 answer
35 views

Inversion array of a given array

Let A[1...n] be an array of n distinct numbers. The ordering of the numbers is any permutation of [1,2,...,n]. An array Inv_A is defined as follows: Inv_A[i] = number of elements A[j] such that j<i ...
2 votes
1 answer
55 views

Are there any problems which are known to be both NP-complete and EXPTIME-complete?

Are there any problems which are known to be both NP-complete and EXPTIME-compelte? My guess is no, because we know that $P$ is not equal to $EXPTIME$ and EXPTIME-complete problems are not in $P$, ...
0 votes
1 answer
27 views

Confusion about NP vs. LINSPACE

I am working through Sipser, and have come accross the following claim, "any $f(n)$ space bounded Turing machine also runs in time $2^{O(f(n))}$", which can be proven by looking at the upper ...
2 votes
1 answer
98 views

Find if a given number must be in a set that is closed under gcd and lcm with some given elements

Source: https://oj.vnoi.info/problem/cryptkey (problem statements are in Vietnamese, so here it is translated). There is a set $S$ of positive integers. If $A$ and $B$ are in $S$, then $\gcd(A, B)$ ...
0 votes
3 answers
52 views

Algorithm with amortized time complexity

While I understand the process of considering/observing an algorithm and finding an average time, necessary to perform an operation that happens in this algorithm, I still cannot quite gasp the idea, ...
  • 185
3 votes
0 answers
39 views

Can fine-grained hardness be proved directly from classical hardness (e.g., $\sf P \neq NP$) in some way?

I have just learnt about some typical result of fine-grained hardness in 15-455 by Prof Ryan: CNF-SETH implies ${\sf DIAMETER} \notin {\sf TIME}(mn^{1-\epsilon})$. (Here DIAMETER stands for the graph ...
  • 191
0 votes
1 answer
24 views

P vs. NP problem and understanding "worst case complexity"

Suppose that $P \not= NP$. Then my understanding is not all instances of NP-complete problems can be solved in polynomial time. That is for every NP-complete problem, there are a colleciton of ...
1 vote
1 answer
25 views

construct language in ${\sf BPP \backslash (RP \cup coRP)}$ assuming $\sf RP \neq ZPP$

Problem This is a HW problem from CMU 15-455 (hw10, p1(a)), spring 17 by Ryan O'Donnell. Assume $L \in {\sf RP \backslash ZPP}$. Define $$ L' = \left\{ (x, y) : \text{either $x \in L$ and $y \notin L$,...
  • 191
1 vote
0 answers
51 views

Do all NP-Complete problems run in $O(c^n)$ time, as opposed to $O(c^{n^k})$?

According to the Wiki article on NP-Completeness, NP-Complete problems can be solved in $O(c^{n^k})$ time (I'll call this EXP-POLY time). However, shouldn't the bound on all their run times be the ...
  • 483
0 votes
0 answers
48 views

How to decide complexity affected by 'magic number'?

Suppose a language $L$ can be decided far more efficiently with a pre-computable (but expensive) 'magic number', then how should we classify the complexity of $L$? For example, if we can only prove $L ...
  • 191
0 votes
0 answers
57 views

Use of break statement in this solution, and time complexity

Note: I had posted this question on Stack Overflow, and got a suggestion to post it to CS Stack Exchange. The original question: You are given a list A of N integers. Here, N is an even number. ...
  • 121
1 vote
2 answers
54 views

Existence of some search algorithms

The lowest time complexity of search algorithms for sorted lists is $$O(n)=logn$$. The lowest time complexity of sorting algorithms is $$O(n) = nlogn$$ So in order to be able to use a search ...
1 vote
0 answers
68 views

LWE with a low rank matrix

Consider the decision LWE setting, where we have to distinguish between $(A, As + e)$ and $(A, u)$, for a randomly chosen $m \times n$ matrix $A$, an $n \times 1$ secret vector $s$, an $m \times 1$ ...
  • 219
0 votes
0 answers
33 views

Is this version of the halting problem NONELEMENTARY?

Input: A TM $M$ and an integer $k$. Output: Yes if $M$ halts within $2\uparrow\uparrow k$ steps (where $\uparrow\uparrow$ is tetration (iterated exponentiation)). Intuitively, it seems like this has ...
  • 1
1 vote
1 answer
46 views

Relation between algorithms and models

I have found this question some time ago. While reading it, I had a problem with understanding the following idea: Question, part 1: Is one allowed to talk about the time/space bound of any algorithm (...
-1 votes
1 answer
71 views

How to resolve the clash between definition of Big O notation and Inductive Hypothesis when proving running time by substitution method?

Suppose you have to prove the solution to the following recurrence by Induction, $$ T(n)= \begin{cases} \Theta(1), & n=1 \\ 2 T(\lfloor n/2 \rfloor)+\Theta(n), & n>1 \end{cases} $$ Here, $\...
  • 149
0 votes
1 answer
20 views

complexity of a function that depends on n%3

...
1 vote
1 answer
124 views

time complexity to convert string to integer and vice a versa

just given solution on this post i had mention the time complexity to convert string to int is O(n), also verifying this post now in one of comment fellow SO user, corrected me with example also ...
1 vote
1 answer
23 views

What is the time complexity of the EMST problem in 3D space

We have an unstructured cloud of $N$ points in 3D space. What is known about the complexity of building the Euclidean Minimum Spanning Tree of the points ? The tree is made of $N-1$ edges and can be ...
  • 6,044
1 vote
1 answer
30 views

Why do we care about computable functions in parametrized complexity definitions?

In a classical definition of the FPT complexity class, for a parametrized problem $L\subseteq \Sigma^* \times \mathbb{N}$ we require an algorithm, solving an instance $(G,k)$ in time $f(k)\cdot n^{O(1)...
0 votes
1 answer
60 views

Is complexity of computing $2^{2^n}$ in P?

According to this answer, given input $2^n$ (and thus input size $n$), this problem is not computable by a deterministic Turing machine in number of steps polynomial in the input size (though it is ...
2 votes
1 answer
49 views

Is there a theorem of the form "for any complexity class $C$ satisfying $X$, there exist $C$-complete problems"?

From what I've read, there are $C$-complete problems for all the complexity classes $C$ that I have looked at: $P$, $NP$, $EXPTIME$, $PSPACE$. But I also know that there is an infinite hierarchy of ...
  • 3,402
0 votes
0 answers
32 views

Baby step giant step algorithm complexity calculation

My question here is mainly a way for me to understand complexity a little better by a confusing example. From what I understand of calculating the complexity of an algorithm, we take the number of bit ...
0 votes
1 answer
46 views

Big O- and Omega-Notation for functions

I want to find out how to check, if the following relationships are true or false. f(n) = nlog(n!); g(n) = nlog(2n^3n); Check, if f(n) = O(g(n)) and/or f(n) = Ω(g(n)) true/false; f(n) = 3n^2; g(n) = 9^...
  • 3
1 vote
4 answers
108 views

What happens to the running time if we reduce the size of input?

Let there is an algorithm whose running time is $O(n^2)$. Suppose we apply a preprocessing step on the algorithm in $O(n)$ so that it reduces the input size to $O(\sqrt{n})$ but doesn't effect the ...
  • 1,437
1 vote
1 answer
62 views

Difference between "almost-linear" and "quasilinear" time complexities

In some works, such as the recent maxflow paper, there is reference to an "almost-linear" complexity, which typically refers to a complexity of $O(n^{1+o(1)})$. This is similar to the notion ...
  • 43
0 votes
1 answer
40 views

Given the current knowledge about complexity class, what can we say?

I am a CS student. I am looking at some questions my professor made and I got stuck in this one. "Which one of the following inclusions between complexity classes is coherent with the current ...
0 votes
1 answer
54 views

How to prove that we can study the complexity of Recurrence Relations by always giving in input a power of how many children each node creates?

Let's say we have the following Recurrence Relation: $$ T(n) = \begin{cases} 1 & n=1 \\ 3T(\frac{n}{3}) + \Theta(n) & \text{otherwise} \end{cases} $$ I've been taught I can ...
0 votes
1 answer
65 views

Find the largest possible number not larger than some integer N and is the product of K consecutive primes

Source: Hanoi student competition of unknown year (Kì thi học sinh giỏi thành phố) Additional conditions: N is a positive integer in range [1, 2^64 - 1] K is a positive integer in range [3, 10] ...
0 votes
0 answers
52 views

Why isn't $P^A = A$?

I have a question regarding oracles. If I have the complexity class $P^A$ (with $P \subseteq A$), what is it's relationship to the class $A$? I mean it should be trivial that $A \subseteq P^A$ for all ...
  • 109
2 votes
1 answer
64 views

Runtime complexity of permutation function

I am trying to find the asymptotic run time complexity of the following function which will return a list of all permutations of nums. ...
2 votes
1 answer
46 views

Simulating nondeterministic RAM with nondeterminstic turing machine

Nondeterminstic RAM is like deterministic RAM with extra instruction “JMAYBE” which nondeterministically jump or continue when executed. According to this paper: An $O(T \log T)$ reduction from RAM ...

1
2
3 4 5
49