Questions tagged [lower-bounds]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
27 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 ...
hsalin's user avatar
  • 733
24 votes
5 answers
48k 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 ...
PleaseHelp's user avatar
22 votes
2 answers
709 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 - ...
R B's user avatar
  • 2,634
21 votes
2 answers
5k 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 ...
Complexity's user avatar
  • 1,187
21 votes
1 answer
656 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 = ...
Knoothe's user avatar
  • 468
19 votes
1 answer
280 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 ...
Erel Segal-Halevi's user avatar
15 votes
4 answers
990 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 ...
Raphael's user avatar
  • 72.3k
11 votes
1 answer
950 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 ...
user834's user avatar
  • 849
10 votes
0 answers
253 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 ...
Kaveh's user avatar
  • 22.2k
9 votes
1 answer
916 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 ...
jsguy's user avatar
  • 619
9 votes
1 answer
8k 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 ...
user5507's user avatar
  • 2,191
9 votes
2 answers
391 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 ...
Open Door Logistics's user avatar
9 votes
2 answers
805 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 ...
orlp's user avatar
  • 13k
9 votes
4 answers
3k 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.'s user avatar
  • 158k
8 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 ...
Complexity's user avatar
  • 1,187
8 votes
2 answers
244 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 ...
Immanuel Weihnachten's user avatar
8 votes
1 answer
655 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 ...
elexhobby's user avatar
  • 299
8 votes
2 answers
841 views

Optimal upper bound on the number of states in the complement of an NFA

I have my own version of lex and I would like to add the complement operation. Derived from that I can then add the intersection and difference also. My version ...
Bryan Olivier's user avatar
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 ...
zeb's user avatar
  • 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 ...
Banach Tarski's user avatar
7 votes
2 answers
3k 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 ...
Igor Markov's user avatar
7 votes
1 answer
338 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 ...
GMB's user avatar
  • 579
7 votes
1 answer
11k 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 ...
MikeKatz45's user avatar
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 $...
pnp's user avatar
  • 753
6 votes
1 answer
292 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 ...
user6818's user avatar
  • 1,135
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?
com's user avatar
  • 3,169
6 votes
1 answer
457 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?
Mohsen Ghorbani's user avatar
6 votes
1 answer
873 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 ...
hengxin's user avatar
  • 9,521
6 votes
1 answer
184 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 ...
Joey Eremondi's user avatar
6 votes
1 answer
902 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 ...
Paul's user avatar
  • 162
6 votes
1 answer
965 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 ...
ShyPerson's user avatar
  • 923
6 votes
1 answer
524 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 ...
Narek Bojikian's user avatar
6 votes
1 answer
1k 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 ...
user avatar
6 votes
1 answer
121 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 ...
user avatar
6 votes
1 answer
244 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. ...
MeyCJey's user avatar
  • 163
6 votes
0 answers
127 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 ...
Vor's user avatar
  • 12.5k
5 votes
5 answers
1k 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 ...
MathCurious's user avatar
5 votes
3 answers
913 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 ...
Christian Pao.'s user avatar
5 votes
1 answer
709 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 ...
vzn's user avatar
  • 11k
5 votes
1 answer
382 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 ...
Sayan Bandyapadhyay's user avatar
5 votes
2 answers
203 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 ...
Nicholas Mancuso's user avatar
5 votes
1 answer
250 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 \...
sdcvvc's user avatar
  • 3,491
5 votes
1 answer
953 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 ...
Cornelius Brand's user avatar
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 ...
neutron-byte's user avatar
5 votes
1 answer
175 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 ...
eig's user avatar
  • 283
5 votes
1 answer
133 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: ...
R B's user avatar
  • 2,634
5 votes
2 answers
3k views

Minimal number of comparisons - sorting $6$ elements

I've been thinking about sorting $6$ elements with the minimal possible number of comparisons. I can do it in $10$ comparisons but I've no idea if this is optimal. Or is there a better algorithm ? ...
user40545's user avatar
  • 563
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, ...
nmore's user avatar
  • 161
5 votes
1 answer
154 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 ...
NightRa's user avatar
  • 506
5 votes
1 answer
347 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 ...
András Salamon's user avatar

1
2 3 4 5