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
0 votes
1 answer
22 views

Are there known super-exponential problems?

Can you point a particular problem, all algorithms solving which are of a super-exponential time-complexity? I know that super-exponential problems exist, but is this a theorem of existence, or can a ...
porton's user avatar
  • 433
0 votes
0 answers
20 views

Is super-exponential complexity useful in practice?

Exponential time-complexity has a useful application in "practical" CS: NP-problems, NP-complete problems. Knowledge about this obviously helps in everyday programming. Can you give an ...
porton's user avatar
  • 433
-1 votes
0 answers
18 views

P with oracle to P is equal to P

How we can prove that P = P with P oracle Can we use this claim: if we have O in P then P with O oracle is in P and the proof for this claim is the following Allowing an oracle can only help compute ...
Rania Djeridi's user avatar
0 votes
1 answer
18 views

How far can we push "counting argument" for proving lower bounds of time complexity?

It's obvious that we cannot find min (or max) in an array of length n in strictly less than n "steps". It's also well-...
e.gryaznov's user avatar
2 votes
0 answers
39 views

Online Pareto Front data structure for sparse high dimensional space

Problem I'm looking for a data structure to incrementally maintain a Pareto Front consisting of tuples in the high-dimensional space $(\mathbb{R} \cup \{\pm \infty\})^K$, with the number of dimensions ...
KarelPeeters's user avatar
1 vote
1 answer
36 views

Linear time alg for checking if numbers in a list are close

Suppose we have an unsorted list of $n$ integers. What is the best algorithm we could use to detect if there exists a pair of ints that are 'close' to each other. Close being within some arbitrary int ...
shrizzy's user avatar
  • 113
-2 votes
2 answers
72 views

Quasi polynomial algorithm for np complete problem

I know that quasi polynomial algorithm is neither polynomial nor exponential. But I want to know if we find such algorithm for NP complete problem, will it be of any use? Or is there such algorithm ...
user's user avatar
  • 11
1 vote
0 answers
25 views

How could higher-order Datalog be more expressive than first-order Datalog?

According to this paper [1], higher-order Datalog is more expressive: ... we demonstrate that on ordered databases, for all k ≥ 2, ...
MWB's user avatar
  • 505
0 votes
0 answers
15 views

Why exactly does constructing a configuration graph of an $s(n)$ space bounded NDTM require that $s$ is space-constructible?

In "Computational Complexity: A Modern Approach", it states that to prove that $NSPACE(s(n))\subseteq DTIME(2^{O(s(n)})$, we can do the following: By enumerating over all possible ...
BreadthFirstTreeSearchFan's user avatar
0 votes
1 answer
36 views

In the proof that $DSPACE(S)\subseteq DTIME(2^{O(S)})$, why precisely do we require that $S=\Omega(\log n)$

I have read and understood various proofs, but have not been able to understand precisely why we require $S=\Omega(\log n)$.
BreadthFirstTreeSearchFan's user avatar
8 votes
1 answer
523 views

Is there a linear-time algorithm for randomly sampling weighted combinations?

For concreteness, here's the specific problem description: suppose we have a set $S$ of $n$ items $a_1, a_2, \ldots, a_n$ with weights $w_1, w_2, \ldots, w_n$ respectively. The goal is to select a ...
Steven Stadnicki's user avatar
0 votes
0 answers
33 views

If this variant of Subset Product remains NP-complete, what other inputs could give me exponential time?

Given $N$ a whole number and a set $S$ of divisors of N, where no repetition is allowed. Decide if there is a combination of divisors with a product equal to $N$. Remove non-divisors from $S$. Remove ...
The T's user avatar
  • 321
1 vote
0 answers
22 views

An optimisation problem involving a special class of polynomials

I'm currently working on an interesting problem in function approximation thta just came to mind and am seeking insights or methodologies that might aid in approaching it. The problem is as follows: ...
AgnostMystic's user avatar
0 votes
2 answers
75 views

If we prove that NP = EXP, does that automatically prove that P != NP?

If P = DTIME(n^c) and EXP = DTIME(2^n), and we prove that NP = EXP, then it means that NP = DTIME(2^n). According to the time hierarchy theorem, the set of languages decided in O(f(n)) is bigger than ...
Aland Ameer's user avatar
0 votes
1 answer
43 views

Prove that $o(g(n)) \cap \omega(g(n))$ is the empty set

This question is from CLRS (3rd Edition). So, I know that this is true, but I can't seem to prove it. My approach was the following: Let $f(n) = o(g(n)) \Rightarrow 0 \le f(n) < c_2g(n)$ for some $...
Arnav Mangla's user avatar
4 votes
2 answers
89 views

Fizz Buzz and pseudo-polynomial time

I am currently taking a course on algorithms, and when reading about the 0/1 Knapsack Problem on Wikipedia I came across a technique which uses dynamic programming and supposedly runs in $O(nW)$ time, ...
414Sigge's user avatar
0 votes
1 answer
24 views

Is $O(n^{f(n)})$ superexponential if $f(n)$ is a polynomial function such that $f(n) > n$ as $n$ approaches $\infty$?

I know that exponential time complexity is $ O(k^n) $, where $k$ is some constant and $n$ is the input size, and that subexponential time is anything slower than that, $o(k^n)$ . If we define ...
Karlo Vizec's user avatar
2 votes
1 answer
65 views

How to solve the recurrence $ T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n} $ in terms of $\Theta$?

I'm attempting to solve the recurrence relation: $$ T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n} $$ in terms of its asymptotic behavior ($\Theta$), specifically using the first case of the ...
Ferran Gonzalez's user avatar
1 vote
2 answers
53 views

How to Solve the Recurrence Relation $T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2$ in terms of $\Theta$?

The provided recurrence relation is as follows: $$ T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2 $$ The goal is to express the solution in terms of the asymptotic notation $\Theta$. Unfortunately,...
Ferran Gonzalez's user avatar
0 votes
1 answer
21 views

How can I reduce the complexity of an inverse DFT where I have a uniform frequency series being evaluated at non-uniform target points?

I have implemented an N-dimensional Non-Uniform Discrete Fourier Transform (in this case it's specifically an inverse NUDFT) using PyTorch. My goal with this implementation is to have a function which ...
kairocks2002's user avatar
1 vote
2 answers
33 views

Can a Code Script be Optimized for Time and Space Complexity Using Logic Gates

let's say that I have a Python script that performs various operations, including data manipulation, conditional logic, and iteration. However, I'm concerned about its time and space complexity ...
edge selcuk's user avatar
1 vote
0 answers
40 views

How could it be the case that NP != EXP? Do we know of any problems in EXP that are not in NP? [duplicate]

I know that NP is a subset of EXP, but I cannot find any resources talking about whether NP = EXP or not. My intuition tells me that any problem that requires exponential time to be solved with a DTM ...
Aland Ameer's user avatar
1 vote
0 answers
28 views

Inefficient double lengthening PRG [closed]

I'm trying to prove that an inefficient double-lengthening PRG exists, i.e. construct a PRG $G: \{0,1\}^n \rightarrow \{0,1\}^{2n}$ My current approach is to bound the number of poly-time non-uniform ...
Stevie's user avatar
  • 141
4 votes
0 answers
69 views

Extending Fagin's Theorem to the Polynomial Hierarchy

Fagin's Theorem (see Wikipedia and these lecture notes) states that there is an equivalence between second-order logic (SOL) formulas with existential quantifiers, and problems in NP. I was wondering ...
UserA2000's user avatar
1 vote
1 answer
554 views

Big-O time complexity for this code snippet

...
Angel's user avatar
  • 11
4 votes
1 answer
112 views

Approximation algorithm with runtime complexity between poly(log(1/eps)) and poly(1/eps)?

Suppose we have an approximation algorithm to some maximization problem, that returns a solution with value $(1-\epsilon)*OPT$. If the runtime of the algorithm is polynomial in the input size and $1/\...
Erel Segal-Halevi's user avatar
3 votes
1 answer
82 views

Is there a language $L$ such that $L \in DSPACE(1) \setminus DTIME(1)$?

It is a very straightforward question. I know that the following holds, and I know why it holds: $DTIME(f(n)) \subset DSPACE(f(n))$ However, is there a language $L \in DSPACE(1) \setminus DTIME(1)$? ...
ampersander's user avatar
1 vote
2 answers
107 views

Time complexity for logarithmic algorithm

I am trying to find complexity for following algorithm. It is from "The Algorithm Design Manual" book. ...
nurgasemetey's user avatar
2 votes
0 answers
67 views

Can a time-optimal algorithm have a time complexity better than its space complexity? [duplicate]

That's what I'm formally asking: Let the algorithm $A$ have the worst-case time complexity $\Theta(f(n))$, such that for any algorithm $B$ with the worst-case time complexity $\Theta(g(n))$ doing the ...
sbh's user avatar
  • 51
0 votes
1 answer
38 views

What is the "big theta" order of the solution of T_n = T_(n/2) + log n, n > 0?

What method(s) could be used to solve this? I am still new to this stuff and would appreciate detailed justification for every step as well as some intuition and the examination of all possible viable ...
user79644's user avatar
1 vote
0 answers
44 views

What are solutions to the convex hull problem?

I have researched multiple solutions to the convex hull problem, but I am afraid I don't really understand some of them. For example, Graham's scan is a bit confusing as it is not very clear if the n ...
user79644's user avatar
1 vote
1 answer
58 views

Time complexity of Jacobi symbol

Here is my algorithm with inputs $a$, which is an integer and $n$, which is an odd natural. Is $\mathcal{O}(n)$ the time complexity of this algorithm? My thoughts: The if-cases in the lines $1$ up ...
Lereu's user avatar
  • 111
3 votes
1 answer
255 views

Time complexity of tree algorithm

I'm new to recurrence relations and master theorem so trying to learn. Say there's an algorithm $A$ whose input is the root of a binary tree $T$. $A$ recurses so that it's called on each and every ...
onepiece's user avatar
  • 133
1 vote
1 answer
38 views

Using time hierarchy theorem to show $Time(n^7)$ strictly contained in P

I'm relatively new to computational complexity and am trying to use the time hierarchy theorem to show that $Time(n^7)$ is strictly contained in P. I understand that the time hierarchy theorem says ...
Lucas's user avatar
  • 11
1 vote
1 answer
157 views

Number of stops during trip - Dynamic programming algorithm

I am attending a course about algorithm design, and I have found an old test which has once been submitted. However, I don't have the solutions to it, and I am having some trouble with one specific ...
FarsoFracico's user avatar
0 votes
0 answers
28 views

If $NP \subseteq BPP$ then $NP = RP$. Confusion on the probability that M gives at least one wrong answer in BPP in n invocations

I was looking at the proof of if $NP \subseteq BPP$ then $NP = RP$ here. At the end of the proof the author states: "Note that if $M$ always gives correct answers on calls to $M$, then when $\phi$...
venturr988's user avatar
0 votes
1 answer
33 views

Conflicting definitions surrounding asymptotic notations. Please advise!

I spent the last couple of days trying to understand the different asymptotic notations but it seems I'm hitting some conflicting information. For context, I believe I've understood the formal ...
ten_to_tenth's user avatar
1 vote
1 answer
48 views

How to prove the time complexity of a function without calculating the precise number of steps taken? (Example: cost of optimal binary search tree)

This is my dynamic programming solution in Python to the problem of finding the cost of the optimal binary search tree: ...
ten_to_tenth's user avatar
2 votes
2 answers
179 views

Analysis of QuickSort Expected Time Complexity: Without Counting the Number of Comparisons

While reading CLRS (4th ed.) regarding the analysis of the expected time for QuickSort, I encountered an alternative approach. The analysis involves the following steps: Given an array of size $n$, ...
Mason Rashford's user avatar
0 votes
1 answer
39 views

Buy two chocolates when want MAXIMUM nonegative spend

This is a self-study inspired by the trivial https://leetcode.com/problems/buy-two-chocolates/. Basically the question is as follows: if you have a value of money m ...
JoeTheShmoe's user avatar
-1 votes
2 answers
253 views

Is the time complexity of a loop that simultaneously increments and multiplies $O(\log_k n)$ when $k = 1$?

Is the time complexity of for(int i=0;i<n;i++){i*=k;} $O(\log_k n)$? The problem is number 8 from GeeksForGeeks: https://www.geeksforgeeks.org/practice-...
HereToTryHelp's user avatar
0 votes
0 answers
16 views

Does $\mathsf{NC_1\subsetneq NC}$ imply $\mathsf{NP\neq coNP}$?

Any $\mathsf{NC}$ circuit could be presented in SAT form via Tseytin transform. This applies in the reverse too: an arbitrary SAT instance could encode any $\mathsf{NC}$ circuit. Now, Frege proof ...
rus9384's user avatar
  • 1,632
4 votes
1 answer
58 views

Max-min one-to-two matching

There are some $n$ people and $2 n$ items. Each person assigns a positive value to each item. The items should be allocated to the people, giving exactly 2 items to each person. The value of a person ...
Erel Segal-Halevi's user avatar
5 votes
1 answer
87 views

"Unbounded" binary search in $\log_2(n) + O(?)$ comparisons

Binary search is the well-known algorithm that compares the input value to an entry in a sorted array, and based on the result then decides to check the same input value against another entry either ...
Albert Hendriks's user avatar
9 votes
1 answer
166 views

Can we solve $\mathrm{MFVS} \leq 1$ in linear (or subquadratic) time?

$\mathrm{MFVS} \leq 1$ is a concise way of writing the following decision problem: Let $G = (V, E)$ be a directed graph. Is there a $v \in V$ such that every cycle in $G$ passes through $v$? (More ...
Mees de Vries's user avatar
1 vote
0 answers
40 views

Is $\mathsf P$ low for every complexity class between itself and $\mathsf{NP}$?

We know that $\mathsf P$ is low for itself. It's also low for $\mathsf{NP}$, $\mathsf{RP}$, $\mathsf{UP}$ and some other complexity classes that contain $\mathsf P$ and are contained in $\mathsf{NP}$. ...
rus9384's user avatar
  • 1,632
0 votes
0 answers
28 views

Is it possible to perform clause-pair minimization on a CNF instance in $o(n^2)$ time?

Let $\varphi(X)$ be a boolean formula in CNF over a set $X$ of boolean variables $x_1,x_2,...,x_n$. Let $c_i$ denote $i^{th}$ clause in $\varphi(X)$. $x_j^0$ denotes $\overline{x_j}$ and $x_j^1$ ...
rus9384's user avatar
  • 1,632
1 vote
0 answers
24 views

Are there any SAT outside of $\mathsf{RP}$ variants that are solvable in quasipolynomial time?

It's possible to construct SAT problems that are solvable in quasipolynomial time, but they are also solvable in polylogarithmic space. Consider, for example, the following problem: Let a set $S$ ...
rus9384's user avatar
  • 1,632
2 votes
0 answers
17 views

Properties of $\mathsf{PH}[1]$ and $\Sigma^{\mathsf P}_{poly(n)}[1]$?

$\mathsf{PH}[1]$ is a variant of a polynomial hierarchy in which each machine can only call its oracle once. $\Sigma^{\mathsf P}_{poly(n)}[1]$ is a polynomially "tall" tower of $\mathsf{NP}[...
rus9384's user avatar
  • 1,632
1 vote
0 answers
47 views

Complexity of an algorithm with nested loops [closed]

How do I calculate the complexity of this Algorithm below? I would like to know how I calculate the sums that form to obtain a formula as a function of n? I know that in general this algorithm has O(n^...
Tony Oliveira's user avatar

1
2 3 4 5
53