Questions tagged [lower-bounds]
The lower-bounds tag has no usage guidance.
241
questions
25
votes
3
answers
8k
views
Is it really possible to prove lower bounds?
Given any computational problem, is the task of finding lower bounds for such computation really possible? I suppose it boils down to how a single computational step is defined and what model we use ...
- 713
24
votes
5
answers
47k
views
Least number of comparisons needed to sort (order) 5 elements
Find the least number of comparisons needed to sort (order) five elements and
devise an algorithm that sorts these elements using this number of comparisons.
Solution: There are 5! = 120 possible ...
- 738
21
votes
2
answers
4k
views
How to prove that matrix multiplication of two 2x2 matrices can't be done in less than 7 multiplications?
In Strassen's matrix multiplication, we state one strange ( at least to me) fact that matrix multiplication of two 2 x 2 takes 7 multiplication.
Question : How to prove that it is impossible to ...
- 1,157
21
votes
1
answer
645
views
Is detecting "doubly" arithmetic progressions 3SUM-hard?
This is inspired by an interview question.
We are given an array of integers $a_1, \dots, a_n$ and have to determine if there are distinct $i \lt j \lt k$ such that
$a_k - a_j = a_j - a_i$
$k - j = ...
- 458
21
votes
2
answers
662
views
Problems that provably require quadratic time
I'm looking for examples of problem which has a lower bound of $\Omega(|x|^2$) for input $x$.
The problem needs to have the following properties:
$\Omega(n^2)$ runtime proof for any algorithm - ...
- 2,624
19
votes
1
answer
269
views
guillotine cuts versus general cuts
Cutting problems are problems where a certain large object should be cut to several small objects. For example, imagine you have a factory that works with large sheets of raw glass, of width $W$ and ...
- 5,894
15
votes
4
answers
955
views
Is every linear-time algorithm a streaming algorithm?
Over at this question about inversion counting, I found a paper that proves a lower bound on space complexity for all (exact) streaming algorithms. I have claimed that this bound extends to all linear ...
- 71.7k
11
votes
1
answer
910
views
Bound on space for selection algorithm?
There is a well known worst case $O(n)$ selection algorithm to find the $k$'th largest element in an array of integers. It uses a median-of-medians approach to find a good enough pivot, partitions ...
- 829
10
votes
0
answers
249
views
Is there a data-structure which is more efficient than both arrays and linked lists? [duplicate]
Background:
In this question we care only about worst-case running-time.
Array and (doubly) linked lists can be used to keep a list of items and implement the vector abstract data type. Consider the ...
- 21.9k
9
votes
1
answer
868
views
$O(\frac{\log n}{\log \log n})$ algorithm for the prefix parity problem
The prefix parity problem can be defined as follows. You are given a string $S$ of length $n$ and initially every character is $0$. Then you want to build a data structure that can support updates ...
- 619
9
votes
1
answer
7k
views
How to use adversary arguments for selection and insertion sort?
I was asked to find the adversary arguments necessary for finding the lower bounds for selection and insertion sort. I could not find a reference to it anywhere.
I have some doubts regarding this. I ...
- 2,171
9
votes
2
answers
376
views
Find the central point in a metric-space point set, in less than $O(n^2)$?
I have a set of $n$ points which are defined in a metric space – so I can measure a 'distance' between points but nothing else. I want to find the most central point within this set, which I ...
9
votes
2
answers
792
views
Is integer sorting possible in O(n) in the transdichotomous model?
To my knowledge there doesn't exist a $O(n)$ worst-case algorithm that solves the following problem:
Given a sequence of length $n$ consisting of finite integers, find the permutation where every ...
- 12.5k
9
votes
4
answers
2k
views
Can element uniqueness be solved in deterministic linear time?
Consider the following problem:
Input: lists $X,Y$ of integers
Goal: determine whether there exists an integer $x$ that is in both lists.
Suppose both lists $X,Y$ are of size $n$. Is there a ...
D.W.♦
- 152k
8
votes
2
answers
241
views
Is there any nontrivial problem in the theory of serial algorithms with a nontrivial polynomial lower bound of $\Omega(n^2)$?
In the theory of distributed algorithms, there are problems with lower bounds, as $\Omega(n^2)$, that are "big" (I mean, bigger than $\Omega(n\log n)$), and nontrivial.
I wonder if are there problems ...
8
votes
1
answer
634
views
Searching the space of permutations
I'm given n objects, and a set of n permutations of these n objects (out of n! total permutations). There is a true underlying permutation, which I know is one among the set of n permutations, but I ...
- 299
7
votes
2
answers
3k
views
Can you do an in-place reversal of a string on a vanilla turing machine in time $o(n^2)$?
By a vanilla Turing machine, I mean a Turing machine with one tape (no special input or output tapes).
The problem is as follows: the tape is initially empty, other than a string of $n$ $1$s and $0$s ...
- 173
7
votes
2
answers
1k
views
Lower Bounds for Size of Independent Set in a Graph?
I recently learnt that for any instance of a k-SAT problem with $m$ clauses and $n$ literals , we have an assignment of literals such that at least $m(1 - 2^{-k})$ clauses are satisfied.
I was ...
- 1,188
7
votes
1
answer
284
views
Implications of the $\Omega(\frac{2^n}{n})$ circuit lower bound being tight
There is a basic result in circuit complexity that says:
There exists a language that cannot be solved with circuits of size $o(\frac{2^n}{n})$.
The argument is a simple counting argument on the ...
- 569
7
votes
1
answer
10k
views
What is an optimal algorithm?
I'm a computer science newbie and I thought I understood cases and bounds when I first studied them. I would take worst case as upper bound and best case as lower bound, but now I know that they are ...
- 193
7
votes
1
answer
4k
views
Lower bound for Convex hull
By making use of the fact that sorting $n$ numbers requires
$\Omega(n \log n)$ steps for any optimal algorithm (which uses 'comparison' for sorting), how can I prove that finding the convex-hull of $...
- 753
6
votes
1
answer
2k
views
How to prove that matrix inversion is at least as hard as matrix multiplication?
Suppose we are given a matrix $A$ over real numbers and we want to computer the inverse of matrix $A$. There are various algorithms to do so and it also turn out that we can use matrix multiplication ...
- 1,157
6
votes
2
answers
2k
views
Lower bounds: queues that return their min elements in $O(1)$ time
First, consider this simple problem --- design a data structure of comparable elements that behaves just like a stack (in particular, push(), pop() and top() take constant time), but can also return ...
- 313
6
votes
1
answer
277
views
Is there an intuitive proof for the existence of hard functions?
I am referring to the theorem on page 115 of the book by Arora and Barak, which states that, ``For every $n>1$, there exists a function $f:\{0,1\}^n \rightarrow \{0,1\}$ that cannot be computed by ...
- 1,105
6
votes
2
answers
2k
views
Space complexity below $\log\log$
Show that for $l(n) = \log \log n$, it holds that $\text{DSPACE}(o(l)) = \text{DSPACE}(O(1))$.
It's well known fact in Space Complexity, but how to show it explicitly?
- 3,139
6
votes
1
answer
345
views
Does finding a cycle with $\log n$ length in $\text{P}$?
Let $G$ be an arbitrary graph with $n$ vertices and we want to find a simple cycle with $\log n$ length. Is there exists a known polynomial algorithm for this problem?
- 537
6
votes
1
answer
866
views
(Nontrivial) Algorithms for finding the third largest element of a set
According to the lecture note by Jeff Erickson, the lower bound for finding the third largest element of a set of $n$ distinct elements is open. See the related post: What is the lower bound for ...
- 9,441
6
votes
1
answer
180
views
Are there any known lower-bounds for complexity on Non-determinsitic machines
For some problems, like sorting, we know that on a deterministic RAM Machine, any comparison sort must take at least $\Omega(n\log n)$ time.
Are they any problems where we have known lower bounds for ...
- 29.5k
6
votes
1
answer
871
views
Lower bound for finding majority element in a sorted array
Suppose $A$ is a sorted array with $n$ elements. I want to know whether we can determine if there are majority elements in $A$ with time complexity $O(1)$.
Recall that a majority element of $A$ is ...
- 162
6
votes
1
answer
943
views
Generalizing the Comparison Sorting Lower Bound Proof
Let's start with the comparison sorting lower bound proof, which I'll summarize as follows:
For $n$ distinct numbers, there are $n!$ possible orderings.
There is only one correct sorted sequence of ...
- 911
6
votes
1
answer
442
views
An example where the algorithm of Hopcroft and Karp performs poorly?
I have been trying to construct an example, where Hopcroft and Karp's algorithm for the maximum matching problem performs poorly (say at least $\Omega(\log n)$ rounds). However, all the examples I ...
- 4,358
6
votes
1
answer
912
views
TM recognizing $0^n1^n$ requires Ω(log n) space
I am trying to prove that any deterministic 1-tape Turing Machine which recognizes the language $L = \lbrace{0^n1^n | n \geq 0 \rbrace}$ requires
$\Omega(\text{log }n)$ space.
I believe this can be ...
user23522
6
votes
1
answer
119
views
Determining if $G$ contains $K_4$ as a minor in polynomial time
I am trying to devise an algorithm for determining if an undirected graph $G$ contains $K_4$ as a minor. I was able to show in a previous problem how to test for $K_{2,3}$ by looking at all pairs of ...
user27145
6
votes
1
answer
202
views
Counting number of swaps to make two strings equal in linear time
The input to our problem is a pair of strings, say $x$ and $y$. We treat our alphabet size as a constant, i.e., our input is effectively a pair of arrays with the values therein bounded by a constant.
...
- 163
6
votes
0
answers
125
views
Problems with Θ(n³) complexity on TMs with lower bounds by communication complexity arguments
One of the most used simple examples of application of Communication Complexity is the $\Omega(n^2)$ lower bound for recognizing palindromes of length $2n$ on a single tape Turing machine.
Is there a ...
- 12.4k
5
votes
5
answers
966
views
Prove a lower bound
Prove: $n^{5}-3n^{4}+\log\left(n^{10}\right)∈\ Ω\left(n^{5}\right)$.
I always get stuck in these types of questions, where there is a $"-(xy^{z})"$ in the expression.
Whenever I see the solutions for ...
- 221
5
votes
3
answers
863
views
Is Green's the best 16-input sorting network so far?
Every paper says that Green's construction is the best 16-input sorting
network as for now.
But why does Wikipedia says: "Size, lower bound: 53"?
I thought "lower bound" meant:"If there exists at ...
- 153
5
votes
1
answer
664
views
space complexity of DFA intersection problem
the DFA-intersection computation problem, given two DFAs specified on the input, compute the intersection DFA, or the decision problem to determine its emptiness, turns out to have wider/ deeper ...
- 11k
5
votes
1
answer
363
views
Linearithmic lower bound for 1-D "distinct" closest pair of points problem
The 1-D distinct closest pair of points problem is as follows: Given a set of n distinct integer points on real line, find a pair of points with the smallest distance between them, here the distance ...
5
votes
2
answers
187
views
Constraint violation and efficiency in search
It seems that (in a broad sense) two approaches can be utilized to produce an algorithm for solving various optimization problems:
Start with a feasible solution and expand search until constraints ...
- 3,857
5
votes
1
answer
241
views
Simple lower bounds against AC0
It is known that $Parity \notin AC^0$ (nonuniform), but the proof is rather involved and combinatorial. Are there simpler, but weaker lower bounds, say for $NP \not \subseteq AC^0$ or $NEXP \not \...
- 3,481
5
votes
1
answer
929
views
Lower bound for sorting n arrays of size k each
Given $n$ arrays of size $k$ each, we want to show that at least $\Omega(nk \log k)$ comparisons are needed to sort all arrays (indepentent of each other).
My proof is a simple modification of the ...
- 1,281
5
votes
1
answer
2k
views
Complexity of determining whether three points are collinear from a set of points
Let $S \subseteq \mathbb{R}^2$ be a finite set of points. Do there exists three collinear points $p, q, r \in S$?
I wan't to know the complexity of this decision problem and present my approach as ...
- 389
5
votes
1
answer
158
views
Lower bound of degree of polynomial approximating parity
Let $\text{MOD}_2 : \{0,1\}^n \rightarrow \{0,1\}$ be a parity function where $$\text{MOD}_2(x_1,\dots,x_n) = \sum_i x_i \bmod 2$$
It is known [See e.g. Lemma 5 of this lecture note] that any ...
- 283
5
votes
1
answer
130
views
Finding a small element in a changing array
Consider having an integer array $A$ with $n$ elements, in addition to any data structure you like.
The array is initialized to zeros.
The goal to to support two operations:
...
- 2,624
5
votes
2
answers
1k
views
Algorithm to find sequence of minimum moves to sort 13 card hand
Just for fun I am trying to write a program to sort the 13 cards (from a standard pack of 52) in a Bridge hand by performing human-like moves on the hand.
A sorted bridge hand is arranged by suit, ...
- 161
5
votes
1
answer
149
views
Corner cases in the Interleave Lower Bound for BSTs
The Interleave lower bound is a lower bound for the amount of operations any Binary Search Tree needs to make for a sequence of accesses. It is used in the construction of Tango Trees, and is based on ...
- 506
5
votes
1
answer
297
views
Size of constant depth circuit for digital comparator?
Is a lower bound of $\Omega(n^2)$ known for the size of any constant depth circuit expressing a digital comparator for two $n$-bit numbers?
Two $n$-bit binary numbers can be compared using a digital ...
- 3,422
5
votes
1
answer
487
views
Average case lower bound for sorting
The $\Omega(n\lg{n})$ lower bound for sorting in the comparison model is well known. Is there a similar average case lower bound for sorting in the comparison model and if so, which random ...
- 860
4
votes
4
answers
2k
views
Is $Ω(n\log n)$ the lower-bound for *all* sorting algorithms or *just comparison-based* sorting algorithms?
Is $Ω(n\log n)$ the lower-bound for all sorting algorithms or just comparison-based sorting algorithms?
If the latter, is it possible for there to be general-purpose sorting algorithms which perform ...
- 421