Questions tagged [lower-bounds]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
25
votes
3answers
7k 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 ...
24
votes
5answers
24k 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 ...
21
votes
1answer
496 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 = ...
19
votes
2answers
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 ...
19
votes
2answers
447 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 - ...
18
votes
1answer
241 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 ...
14
votes
4answers
836 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 ...
11
votes
1answer
748 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 ...
10
votes
0answers
223 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 ...
9
votes
2answers
290 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
2answers
576 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 ...
9
votes
4answers
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 ...
8
votes
2answers
232 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
1answer
676 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 ...
8
votes
1answer
563 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 ...
8
votes
1answer
6k 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 ...
7
votes
2answers
691 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 ...
7
votes
2answers
2k 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 ...
7
votes
1answer
126 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 ...
7
votes
1answer
3k 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 $...
6
votes
2answers
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 ...
6
votes
1answer
206 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 ...
6
votes
2answers
1k 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?
6
votes
1answer
268 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?
6
votes
1answer
844 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 ...
6
votes
1answer
156 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 ...
6
votes
1answer
780 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 ...
6
votes
1answer
830 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 ...
6
votes
1answer
566 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 ...
6
votes
1answer
107 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 ...
6
votes
0answers
119 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 ...
5
votes
3answers
719 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 ...
5
votes
1answer
517 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 ...
5
votes
1answer
288 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
2answers
175 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 ...
5
votes
1answer
224 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 \...
5
votes
1answer
791 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 ...
5
votes
1answer
1k 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 ...
5
votes
1answer
115 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 ...
5
votes
1answer
118 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: ...
5
votes
2answers
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, ...
5
votes
1answer
105 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 ...
5
votes
1answer
4k 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 ...
5
votes
1answer
159 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 ...
4
votes
4answers
979 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 ...
4
votes
3answers
1k views

Why is the lower bound of element uniqueness in $\Omega(n\log n)$?

I wish to discuss the element uniqueness problem. First let's define the problem: Definition from wikipedia: In computational complexity theory, the element distinctness problem or element ...
4
votes
3answers
76 views

What is the difference between saying there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time and $n^{2-o(1)}$ or $\Omega(n^2)$?

I have seen the formulations there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time a problem requires time $n^{2-o(1)}$ a problem requires time $\Omega(n^2)$ being used ...
4
votes
1answer
205 views

Lower bound on running time for solving 3-SAT if P = NP

Is there a lower bound on the running time for solving 3-SAT if P = NP. For instance, is it known that 3-SAT can't be solved in linear time? What about quadratic?
4
votes
1answer
635 views

Determining if an integer appears more than $n/2$ times

What is the minimum number of comparisons required to determine if an integer appears more than $n/2$ times in a sorted array of $n$ integers? I am trying binary search on the array A. Algorithm(A): ...
4
votes
1answer
2k views

Complexity of transposing matrices represented as list of row or column vectors

Given [[1,4,7],[2,5,8],[3,6,9]] which is a list of the column vectors of matrix |1, 2, 3| |4, 5, 6| |7, 8, 9| is $ \Omega(n^2) $ a lower bound for transposing? ...

1
2 3 4 5