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,740 questions
3
votes
2
answers
117
views
Time complexity of a backtracking algorithm
I just solved the following Leetcode problem: All Paths From Source to Target
Here is my solution:
...
- 127
3
votes
3
answers
186
views
Finding longest fibonacci substring in a given string in linear time
Fibonacci string is a sequence of strings defined by $F_1 = \mathtt{a}$, $F_2 = \mathtt{b}$, and $F_{n+2} = F_{n}F_{n+1}$ (concatenation). For example, $F_3 = \mathbb{ab}$, $F_4 = \mathbb{bab}$, etc.
...
- 33
2
votes
1
answer
227
views
Knapsack problem with bounded value/cost ratios
Consider an instance of the knapsack problem: there are some $n$ items, each with a value and a cost. We should choose a subset of items with total cost at most $C$, and subject to that, with a ...
- 6,131
2
votes
1
answer
91
views
Tighter than exponential time bound for DSPACE
Hi I was wondering whether there is a tighter bound on the time complexity in the following theorem:
$$
\mathrm{DSPACE}(f(n)) \subseteq \mathrm{DTIME}\left(2^{O(\log n+f(n))}\right).
$$
In particular, ...
- 177
0
votes
0
answers
5
views
Can Renamable Horn Sat be solved directed using unit propagation without reduction to Horn Sat?
I am looking into Sat Solvers and I have subproblems which I know are renamable Horn Sat.
Was wondering if I can speed up my solutions by using unit directly on renamable Horn Sat rather than reduce ...
2
votes
1
answer
50
views
Time complexity analysis of Tseytin transformation
Hi I was looking at a proof and in the proof it is used that SAT can be reduced CNF-SAT, in polynomial time. If I am correct this is accomplished through a Tseytin transformation, the wikipedia ...
- 177
1
vote
1
answer
20
views
Conversion of regular Turing Machine to oblivious Turing Machine with minimal overhead
I was wondering when converting a Turing Machine machine into a corresponding oblivious Turing machine, how efficiently the oblivious equivalent can be run in function of T(n) the maximum number of ...
- 177
1
vote
0
answers
21
views
Lower bound on universal turing machine simulation time
Hi I was wondering for a universal (deterministic) turing machine $U_{TM}$ that simulates a pair $<TM,\sigma>$ with $\sigma \in \Sigma^*$ with $T(n)$ the number of steps $TM$ takes when run on $\...
- 177
0
votes
0
answers
73
views
Bounded Quadratic Congruence problem variants (bound is a function of $b$)
Given: 3 positive integers $a$, $b$, $L$.
Problem: Is there a positive integer $x \leq L$ such that $x^2 \equiv a \pmod b$?
This problem remains NP-complete (AN1 G&J) even if the factorization of ...
- 797
1
vote
1
answer
52
views
Parameter selection and Big-O notation
This may seem like a pedantic or trivial question but it's something that's been irking me since working through some problems in a competitive programming manual.
One of the problems dealt with ...
- 11
0
votes
2
answers
45
views
Subtree of Another Tree Complexity: Alternative Solution Analysis
To find out if a tree is a subtree of another, there is an O(m*n) complexity solution that I'm aware of, that looks a bit like:
...
0
votes
1
answer
52
views
Is every discrete problem solvable in constant time for input within a given range of values?
Given arbitrarily large (but not infinite) memory is it possible to compute and store every possible output for every possible input beforehand thus making the program run in constant time?
- 103
0
votes
0
answers
22
views
Complexity of determining whether a given probability distribution has maximal entropy
Let $W\neq\varnothing$ be a finite set of states and $\partial:W\rightarrow[0,1]$ a (rational) probability distribution on it. The size of $\partial$ is the number of non-zero terms in it. E.g., for $...
2
votes
0
answers
74
views
Find all non-extendable ranges in an array of real values with a non-positive sum
I have a long array of size $n>10^6$, call it $X$. I would like to find all ranges $[a, b)$ satisfying the following conditions
$\sum_{i=a}^{b-1}X[i] \leq 0$,
$b-a \geq K$,
$\sum_{i=a-1}^{b-1} X[i]...
- 21
4
votes
1
answer
92
views
Complexity record for solving univariate quadratic equation over finite field
Given a finite field of order $2^{\lambda}$ (where $\lambda$ isn't integral), what's the time complexity of finding any solution of the equation $ax^2+bx+c=0$ in the said finite field?
The best ...
- 450