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,731 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
2
votes
0
answers
39
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]...
4
votes
1
answer
65
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 ...
2
votes
1
answer
77
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 ...
0
votes
1
answer
56
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
vote
0
answers
62
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
124
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$ ...
0
votes
1
answer
112
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, ...
1
vote
2
answers
433
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
202
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)$ ...
1
vote
2
answers
125
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
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
93
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^{\...
1
vote
1
answer
150
views
How fast can cyclic shift be implemented?
How fast can cyclic shift of size $n$ be implemented? Lets say the input is a string of length $n+ \log_2 n$ where the last $\log_2 n$ tell the function how much to shift the first n digits.
I know ...