# 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,156 questions
Filter by
Sorted by
Tagged with
56 views

### Quasilinear time algorithm for 3-SAT

Is it consistent with the current knowledge that there is an algorithm solving a 3-SAT instance in $n$ clauses in quasilinear time in $n$?
43 views

### what is the time complexity of this for for for if

I need to know the analysis of time complexity of this case? ...
278 views

### Best algorithm to find "deepest" interval

Let's say I have a list of intervals on a number line. The "depth" of a point on this number line corresponds to the number of intervals in the list that contain it [the point]. So for ...
34 views

### Computational Complexity of 3SAT variant with additional restrictions on variables/clauses

Given a 3SAT problem with the additional constraints that: No clause or set of clauses is the 3SAT instance is 'redundant'. Thus, this 3SAT cannot eliminate any clauses. For any/every clause, the ...
39 views

### Disambiguating Big-O and Theta for Expressing Time Complexity

Can someone please give me an example of two algorithms, one where "Big-O" is the most appropriate expression of how time complexity grows with input size, and one where this would be Θ? Can ...
33 views

### CVAL is in P (technical detail)

I would like to clarify to myself the way that an algorithm that proves the statement in the title works: I think the idea should be like this: We assign the input values to the bit nodes We ...
44 views

### Why can't we use BFS with modifications to find shortest paths in weighted graphs

I came across this post about how we can get to all shortest paths from source (u) to destination (v) . If the algorithm is working in O(E + V), why can't we use it (after slight modifications) for ...
33 views

82 views

### How to prove time complexity for this algo?

I have an intuition that this algorithm should have o(n) time complexity but I cannot prove it rigorously. The question is as follows: Suppose you have an n×n 2-dimensional array A such that each row ...
49 views

### How to encode a Universal Turing machine to an Integer $\in\mathbb{N}^+$?

The proof of Hierarchy Theorems (including space hierarchy theorem, deterministic time hierarchy theorem, nondeterministic time hierarchy theorem) depend on constructing a Universal Turing machine ...
73 views

### my dsa teacher gave a assignment which is really confusing (i asked my teacher about it but she said just google it and find it out yourself) [closed]

Write best case, worst case and average case time complexity of following categories of algorithm– a. Constant time b. Linear time c. Logarithmic time d. Polynomial time e. Exponential time (this ...
87 views

### I want to show, without taking a limit, that $2^\sqrt{2 \log n} \in Ω(\log^2n)$ and $2^\sqrt{2 \log n} \in O(\sqrt{2}^{\log n})$

I want to show, without taking a limit, that $2^\sqrt{2 \log n} \in Ω(\log^2n)$ and $2^\sqrt{2 \log n} \in O(\sqrt{2}^{\log n})$. I will omit what I have tried as it has not been useful.
71 views

### What is the computational complexity in big O notation of an algorithm computing n^n?

I have a number n of size s. What is the computational complexity in big O notation of an algorithm computing n^n? Let's assume I'm using exponentiation by squaring. The result size doubles when we ...
### is it true that if $f(n)\in O(g(n))$ then $f(h(n)) \in O(g(h(n)))$?
is it true that if $f(n)\in O(g(n))$ then $f(h(n)) \in O(g(h(n)))$? I can't figure out how to prove or disprove this. if it is true, is it true only when the function $h$ is invertible?
### What's the time complexity of finding all size-$k$ combinations from a set of size $n$?
I'm wondering what's the time complexity of finding all size-$k$ combinations from a set of size $n$(note that $k$ is a known and fixed constant, say $k=3$)? How does it differ from the time ...