Questions tagged [lower-bounds]

The tag has no usage guidance.

227 questions
Filter by
Sorted by
Tagged with
589 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 ...
153 views

Sorting array with two elements - in place and minimal number of comparisons, lower bound

Algorithm must be in place. I would like to find lower bound for comparison algorithm. Algorithm will sort array with only two elements - without loss of generality let assume that there are only $1s$ ...
149 views

Partition array - elements non-negative and negative. Minimal number of replacements of elements

I consider following problem: It is given array with numbers, for example $[-2,0,1,-324,213,321,-2]$. The problem is: replace elements such that negative numbers precede the non-negative. For our ...
909 views

Why doesn't decision tree work in case find minimum

When we would like to prove lower bound comparison algorirthm, we often use decision tree, for example sorting by comparisons. So let's consider find minimum in array $a[1..n]$ by comparison. Lower ...
203 views

Minimum exchanges for heap sort

I'm studying heap sort and was presented with the following question. What is the minimum number of items that must be exchanged during a remove the maximum operation in a heap of size N? Give a ...
305 views

Comparing two graphs [closed]

I want to compare the vertices of two graphs. Given two graphs, $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$, I want to compare $u_n$ and $v_m$ for $u \in V_1$ and $v \in V_2$. I came up with double ...
74 views

lower bound of checking if in array are two different elements [closed]

Considering the lower limit to the problem of checking whether the array are only the same number via comparisons. And thnik about $n-1$. Consider the diagram hasse. This diagram must be consistent (...
2k 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 ? ...
129 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 ...
3k views

If an NP-complete problem is shown to have a non-polynomial lower bound, would that prove that P != NP?

I understand that the Cook-Levin theorem proved that any NP problem is reducible to an NP-complete problem, which signifies that if a polynomial-time algorithm for an NP-complete problem is found, it ...
43 views

number of comparison in sort algorith with special operation

Let's define: $a_i:a_j \Longleftrightarrow a_i < a_j;\ a_i=a_j;\ a_i > a_j$ So it is similiar to normal operation $<$, but $:$ give information when elements are equal. I want show that ...
321 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 ...
37k 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 ...
4k 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?
369 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 ...
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, ...
714 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 ...
224 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 ...
225 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 ...
361 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.
721 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 ...
321 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 ...
595 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 ...
820 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 ...
49 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 ...
776 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 ...
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 ...
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 ...
71 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 ...
108 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 ...
69 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 ...
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 ...
352 views

149 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 ...
138 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. ...
312 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 ...
117 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. ...
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 ...
180 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 ...
410 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 ...
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 ...