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,732 questions
0
votes
0
answers
9
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
53
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
66
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 ...
- 448
2
votes
1
answer
85
views
Stateless Modeling of Stochastic Systems
Let $f : S \times \mathbb{N} → \mathbb{Z}$ be a stochastic function seeded by $\mathrm{seed} \in S$, constrained such that
$$
|f(\mathrm{seed}, t + 1) - f(\mathrm{seed}, t)| \le 1
$$
Such a function ...
- 163
0
votes
1
answer
57
views
Repeating a PSPACE problem exponentially many times
I am trying to understand the complexity of a problem that involves solving some $\mathsf{PSPACE}$-complete problem exponentially many times. Namely, one can imagine $\Xi=\{\phi_1,\ldots,\phi_n\}$ to ...
0
votes
0
answers
30
views
What is the difference in number of bit operations in the given expressions using big O notation?
What is the difference in the number of bit operations in the given expressions using big O notation:
$\sum_{i=1}^n i^2$
$\frac{n(n+1)(2n+1)}{6}$
For 1. there are $n$ additing bit operation and $n^2$...
- 1
1
vote
0
answers
66
views
Find a minimal binary tree that satisfies lowest common ancestor constraints
I want to find if there's a fast algorithm for the following:
Given a set of lowest common ancestor constraints, find the smallest (fewest number of nodes) strict binary tree that satisfies all of ...
0
votes
3
answers
128
views
Why do we typically give algorithmic complexities through big O?
I mean, we could in principle use $\Theta$, $\omega,o$ and so on but it seems so that $O$ is a favourite in presenting computational complexities. Why?
1
vote
0
answers
64
views
Can the group-structure of my constraint reduce the corresponding assignment problem to polynomial time search complexity?
Consider a finite Abelian group $G$ where each element is its own inverse. As an explicit example, let $G$ be the integers 0 to 31 under the bitwise XOR $\oplus$ operation. We have a collection of $n$ ...
- 11
0
votes
1
answer
114
views
Time complexity in RAM vs Turing machine
A very basic question has bugged me for a while. We know that random-access machines (RAM) are polynomially equivalent to Turing machines. I assume the RAM model to have unit cost addition, ...
- 3,413
1
vote
2
answers
463
views
What is the most efficient algorithm for partitioning a list into roughly equal sections?
I started thinking about this problem while trying to find the best way to divide a book reading into $4$ roughly equal sections. I ended up brute-forcing every possible combination, but now I'm ...
1
vote
1
answer
205
views
Can we solve Parity Games in polynomial time given this subroutine?
Parity games are simple games played on a graph: https://en.m.wikipedia.org/wiki/Parity_game
Let $A$ be an algorithm that solves the following problem in polynomial time.
Given: A graph $G=(V,E)$ ...
- 55
1
vote
2
answers
127
views
Time complexity of adding $n$ numbers with $n\log n$ bits each
I'm trying to determine the time complexity of adding $n$ numbers that each have a bit length of $n\log n$. I'm confused because sometimes I've seen the addition of two $n$ bit numbers as requiring $O(...
- 1,703
1
vote
0
answers
92
views
Time complexity hierarchy
I am trying to understand the proof of the following theorem, as given by Sipser for example.
If a function $t$ is time-constructible, then there is a language that is decidable in time $t$ but not ...
2
votes
1
answer
94
views
can Strassen's matrix multiplication algorithm be parallelized?
Just want to check when you parallize Strassen's algorithm you get a time complexity of $O(\log n )$ because you divide and conquer $\log n$ times in parallel and a space complexity of $ O( n^{\...
- 21