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
3 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
37 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
28 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
0 answers
11 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
-2 votes
0 answers
36 views

Algorithm Design Manual Chapter 2 Question 5

for k = 1 to n: x = k while x < n: print "*" x = 2x We're having a hard time proving that the time complexity is $\Theta\left(...
SReza S's user avatar
1 vote
2 answers
31 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
39 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
27 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
68 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 votes
0 answers
125 views

Complexity of counting number of 3-literal set

Problem : Given a Set A of 3 sets each set inside Set A contains 2-literal subsets ,find how many unique 3-literal set we can make by selecting exactly one subset ...
Anuj's user avatar
  • 41
-1 votes
0 answers
17 views

I have solved this question 80% and I am stuck in squeezing the series.the question is : T(N)=4T(n/2) + n^2/log n

Please solve it using iterative method only. The question is of recurrence relation T(N)=4T(n/2) + n^2/log n I am stuck at solving the log n series At the end I am getting following: 4^kT(N/2^k)+n^2( ...
VENUS CHAUDHARY's user avatar
1 vote
1 answer
549 views

Big-O time complexity for this code snippet

...
Angel's user avatar
  • 11
2 votes
0 answers
41 views

Is there a function between poly(log(n)) and poly(n)?

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
81 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
66 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
39 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
55 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
205 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
114 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
18 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 ...
ideals_go's user avatar
  • 113
1 vote
1 answer
45 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: ...
ideals_go's user avatar
  • 113
2 votes
2 answers
170 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
36 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
229 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
15 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,600
4 votes
1 answer
55 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
84 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
165 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
34 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,600
0 votes
0 answers
27 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,600
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,600
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,600
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
0 votes
2 answers
58 views

How to compute the complexity of $T(n) = 2T(\frac{n}{2}) +O(n\log n)$

I'm trying to solve the recurrent $$T(n) = 2T\left(\frac{n}{2} \right) +O(n\log n)$$ I thought about Master's theorem but unfortunately, my recurrent doesn't belong to any cases Could you please help ...
Pipnap's user avatar
  • 101
0 votes
0 answers
45 views

What's the time complexity of it?

I wrote a pseducode for the Algorithm I am interested in its time complexity. Here is algorithm: ...
foragerDev's user avatar
0 votes
1 answer
59 views

Find multiple order-statistics of an array

Given array $a$ of size $n$ and array $p$ of size $m$. How we can for every $i < m$ find $p_i$-th order statistics of array $a$ in $O(m log(n) + n)$? We can find order statistics separately, but it ...
  mozhayka's user avatar
1 vote
1 answer
207 views

How do I find time complexity of while loops?

I am designing a simple algorithm to be used at hardware level. And I want to find its time complexity. i=1 while(i<=n) { i=i*2; } How I'd go about finding ...
barnyard9's user avatar
0 votes
1 answer
29 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 ...
rus9384's user avatar
  • 1,600
1 vote
0 answers
40 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 ...
HelpmePlease's user avatar
1 vote
0 answers
59 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 ...
Fireond's user avatar
  • 11
0 votes
1 answer
52 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) ...
Vedant Khandelwal's user avatar
1 vote
1 answer
29 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\}^*$ ...
KJL's user avatar
  • 13
0 votes
2 answers
65 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: ...
john doe's user avatar
  • 177
1 vote
1 answer
127 views

Time complexity of algorithm with three loops and if statement

Suppose I have this c++ code: ...
john doe's user avatar
  • 177
0 votes
1 answer
34 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 ...
Yannik Eik's user avatar
1 vote
0 answers
26 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 ...
Shisui's user avatar
  • 121

1
2 3 4 5
53