# Questions tagged [lower-bounds]

The tag has no usage guidance.

214 questions
Filter by
Sorted by
Tagged with
3answers
3k views

### In complexity, why do we find upper bounds, not lower bounds?

In algorithms we use to find Big-O (upper bound), Big-omega (lower bound) and Big-Theta but why we are always interested in finding upper bounds instead of lower bounds?
2answers
308 views

### Can you get O(n) with a word frequency algorithm?

By a word frequency algorithm: An algorithm gets a document as an input, and returns each unique word along with the number of times it has appeared in the document. For example: in:"Hello my name ...
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, ...
1answer
597 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 ...
1answer
202 views

### Lower bound for maxima on 2D plane

Given $n$ points $(x_1, y_1), \ldots, (x_n, y_n)$ on a 2-dimensional plane. A point $(x_1, y_1)$ dominates $(x_2, y_2)$ if $x_1 > x_2 \land y_1 > y_2$. A point is called a maxima if no other ...
1answer
208 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 ...
1answer
331 views

### Quadratic lower bound for deciding the set of palindromes

How to prove a single tape Turing machine needs at least n squared time to decide palindrome? This is an exercise from the "computational complexity - a modern approach" book.
2answers
624 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 ...
1answer
254 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 ...
1answer
572 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 ...
1answer
794 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 ...
1answer
46 views

### Particular function communication complexity computation

Consider a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$. If $f$ satisfies $f(\bar{0})=0$ where $\bar{0}$ is vector of $0$, $f(x)=1$ with every $0/1$ vector of hamming weight $1$, then ...
2answers
731 views

### Morgenstern proof for FFT lower bound

I looked at my notes from a class about fast forier transform , and the professor proved in class theorem thanks to Morgenstern , first he defined linear algorithm as a algorithm that inly uses ...
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 ...
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 ...
1answer
70 views

### Lower bounds for space with some probability of error

There is an information theoretic lower bound of $\log_2 {U \choose x}$ for the number of bits to represent a subset of $x$ elements chosen from a universe of size $U$. We can in principle use this ...
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 ...
1answer
68 views

### Lower-bounds of a given problem

I have the following problem: You have n objects that have identical weight except for one that is a bit heavier than the others. You have a balance scale. You can place objects on each side of ...
1answer
58 views

### simple lower bound for constructing a Spanning tree

i have to demonstrate that under the assumptions{Bidirectional Links, Total Reliability (no error during the execution), Connectivity, Distincts ids values, Multiple inititators (entities that starts ...
1answer
311 views

1answer
148 views

### exponential lower bound on boolean formula conjunctions, what complexity class? [closed]

This new paper A Lower Bound for Boolean Satisfiability on Turing Machines by Hsieh asserts an exponential lower bound for a TM time complexity on a problem of finding whether a solution exists to a ...
1answer
132 views

### Lower-bounding the Membership Problem in the Bitprobe Model

I am working through the following paper "Data Structures for Storing Small Sets in the Bitprobe Model" by Radhakrishnan et al. and am confused regarding one of their arguments about a lower bound. ...
1answer
292 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 ...
1answer
108 views

### Lower bound on number of comparisons needed to search for a number in a sorted 3-d array

Suppose we have an $N \times N \times N$ 3-d sorted array meaning that every row,column, and file is in sorted order. Searching for an element in this structure can be done using $O(N^2)$ comparisons. ...
1answer
1k views

### Traveling Salesman: how to use a lower bound?

Let me preface this question by giving some helpful background material. I'm trying to solve the traveling salesman problem using branch and bound. Concretely, for a partial solution, I'm using the ...
1answer
139 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 ...
0answers
395 views

### Trying to understand the Gilmore-Lawler lower bound

For a class project we're developing a software that solves a common optimisation problem. After some research we've found out that our problem is called QAP (Quadratic Asssignment Problem) and the ...
1answer
55 views

### Help in geometrically understanding “Linear Decision Trees”

In the words of (http://www.cs.utah.edu/~suresh/5962/lectures/17.pdf, section 17.2), "Each $f(x)$ can be interpreted as deﬁning a hyperplane in $R^n$. Thus, tracing a path through the tree computes ...
1answer
155 views

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? ...
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 ...
2answers
2k views

### Methods for Finding Asymptotic Lower Bounds

I've found in many exercises where I'm asked to show that $f(n)=\Theta(g(n))$ where the two functions are of the same order of magnitude I have difficulty finding a constant $c$ and a value $n_0$ for ...
0answers
226 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 ...