# 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,666 questions
Filter by
Sorted by
Tagged with
1 vote
10 views

### Solving big O formula

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 ...
• 13
1 vote
27 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 ...
• 33
139 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 ...
• 33
45 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. ...
• 990
43 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? ...
• 27
1 vote
47 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 ...
80 views

• 255
1 vote
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
98 views

30 views

### How is the prefix function (for KMP) time complexity O(N)?

I'm looking at the algorithm for the prefix function from here https://cp-algorithms.com/string/prefix-function.html : ...
• 324
53 views

### Is this how I could come up with the time complexity for the Sieve of Eratosthenes?

So here is how I tried to come up with the time complexity for the Sieve of Erast. According to Wikipedia it is $O(n \; \text{log} \;\text{log}\;n)$. I got $O(n \; \text{ln}(\sqrt{n}))$ Here is what I ...
• 31
52 views

### Complexity class BPP, but with only expected polynomial running time

The complexity class BPP requires that the running time be guaranteed polynomial, though with only a 2/3 chance of the correct output. ZPP, on the other hand, guarantees correct output, but now only ...
61 views

1 vote
53 views

### Understanding Time Complexity Calculation for Factorial and Exponential Algorithms

I'm trying to wrap my head around how to calculate the time complexity of algorithms that exhibit factorial (𝑛!) or exponential (2^𝑛) growth rates. Specifically, I want to understand the thought ...