Questions tagged [lower-bounds]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
2
votes
1answer
237 views

Lower Bound for Sorted 2-Sum

Given a sorted array of integers $x$ and a target value $t$, determine if there exists a pair $x_i, x_j \in x \wedge i \neq j$ such that $x_i + x_j = t$. What is the lower bound for this problem? I ...
5
votes
1answer
129 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 ...
0
votes
1answer
935 views

How to solve a knapsack problem with increased weight limit?

Let us consider the knapsack problem. Given a set $P$ of $n$ items where each item has weight $w_i$ and value $v_i$ for all $i=1,2,\ldots,n$. We have two bins, one has a weight limit of $W$ and the ...
2
votes
0answers
142 views

Finding post-order traversal of a binary tree from its in-order and pre-order traversals lower bound

I know that we can construct a BST by just having its pre-order traversal in $O(n)$ time (this link). But what if the tree is just a binary tree and we have its in-order and pre-order traversals? I ...
3
votes
1answer
157 views

Evasiveness of acyclicity of undirected graph

The lecture note by Jeff Erickson discusses "Evasive Graph Properties": We call a graph property evasive if we have to look at all $\binom{n}{2}$ entries in the adjacent matrix to decide whether ...
1
vote
1answer
886 views

Can we count the number of inversions in time $\mathcal{O}(n)$?

It is possible to find the total number of inversions by $\mathcal{O}(n\log{}n)$ running time (extension of merge-sort algorithm for example). Is there more asymptotically efficient way to do it? $\...
0
votes
1answer
633 views

Lower bound on worst case pancake number?

Given n pancakes, for each permutation we can compute the minimum number of pancake flips. If we take the maximum over all possible permutations, we get the worst case pancake number $P_n$. I think ...
1
vote
1answer
279 views

Why is the lower bound $m \log n$ for this make-set, union and find-set sequence?

Look at this solution: Is the lower bound $m\log n$ because we are only looking at the lower bound for union by rank only? If we make $n$ MAKE-SET operations, then there would be $\log n$ UNION ...
3
votes
1answer
2k views

Lower bound for $k$-sorting an array

This is exercise 2 of the lecture note by Jeff Erickson on decision tree lower bounds. We say that an array $A[1 \ldots n]$ is $k$-sorted if it can be divided into $k$ blocks, each of size $n/k$ (we ...
3
votes
1answer
85 views

Original literature on adversary argument

I want to know about the early invention/use of the adversary argument (see the lecture note by Jeff Erickson) which is a technique for establishing lower bounds of problems. I cannot find the ...
6
votes
1answer
849 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 ...
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 ...
2
votes
1answer
608 views

Lower bound on the number of comparisons needed for finding the two largest elements

Given a sequence of ݊different elements, there is an algorithm that finds the maximum element, and the 2nd largest element, using n +log_2(n) - 2 comparisons. Prove that any algorithm will have to ...
3
votes
1answer
333 views

How to prove that Inner product of two $n$ dimensional vectors requires at least $n$ many multiplications?

Input : Two matrices $A$ and $B$ of size $n$ X $n$. Compute : Matrix product $A$ X $B$. Some of the known results about matrix multiplication are given below. Brute Force : $O(n^3)$. Nader H. ...
4
votes
1answer
268 views

lower bound for Renyi–Ulam Game with lies

Player $A$ thinks of number between 1 and $n$ and ask $B$ to guess the number with minimum number of decision queries (yes or no type ). Game : $A$ chooses an element in {1,2....,n} $B$ tries to ...
5
votes
1answer
204 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 ...
2
votes
1answer
127 views

Why is $\Omega(\log\log n)$ a lower bound for the depth of polynomial-width circuits computing parity?

I'm working on an exercise from The Nature of Computation concerning polynomial-width circuits computing parity. In particular the exercise asks to sketch a proof that the depth of such a circuit has ...
4
votes
1answer
1k 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): ...
1
vote
1answer
382 views

Sorting using comparison is superlinear or sublinear?

My question is, is comparison based sorting problem, in time complexity, a superlinear problem or a sublinear problem? In more details: we know that sorting using comparison have the achievable lower ...
2
votes
1answer
836 views

Precise relation between complexity classes(focus on P, NP and EXPTIME)

I am interested in the precise relation between $P$, $NP$ and $EXPTIME$ classes. What I know so far: $P \subseteq EXP$ (from Time Hierarchy Theorem [1]) We don't know an exact relation between $P$ ...
1
vote
1answer
2k views

How to use the Pigeonhole Principle to prove a DFA has a minimum number of states?

$A = \{w \in \{a, b\}^* | $ 10th character from the end of $w$ is $b\}$ Prove if DFA $M$ has $L(M) = A$ then $M$ has at least 1024 states. So there's only 2 characters possible at any state, aside ...
3
votes
1answer
91 views

Complexity of sorting $A+A$

Is there a proof for the lower bound of the problem to create a sorted list of sums for a given list of integers with length n. In this [thread][1] people discuss solving this problem by sorting the ...
-1
votes
2answers
1k views

Deleting edges from complete graph

I have a complete undirected graph with $V$ vertices and $\frac{V(V - 1)}{2}$ edges. Then, I remove $K$ edges $(a_i, b_i)$. I want to know if the graph is still connected after performing all the ...
2
votes
1answer
125 views

Examples for lower bounds proof except sorting

After i read this question here. All non-trivial examples of lower bounds always mention sorting, but i do not find other non-trivial examples, which do not rely (partly) on the sorting proof. What ...
3
votes
1answer
986 views

Is there a decision algorithm with time complexity of Ө(n²)?

Is there a decision problem with a time complexity of Ө(n²)? In other words, I'm looking for a decision problem for which the best known solution has been proven to have a lower bound of N². I ...
0
votes
1answer
540 views

Adding Big-O and little-o notation to get a little-o

Lets suppose that there exists a comparison-based algorithm that turns an arbitrary array to a state $A$ in $o(n\log k)$, and there is another comparison-based algorithm that turns an array in state $...
2
votes
1answer
165 views

Linear time algorithms on regular graphs

For each constant $k$, the number of $k$-regular graphs is of the order of $n^{\Omega(n)}$. Therefore, we need $O(n\log n)$ bits to represent k-regular graphs unambiguously. Let $k=3$ for simplicity....
0
votes
1answer
51 views

What is the best terminology for lower bound

The term lower bound comes from math and applies to more than just complexity theory. What we see is that such and such is "a" lower bound. In complexity theory should this not be phrased as "the" ...
0
votes
1answer
156 views

Sorting algorithm which sorts half the possible inputs in linear time

Prove that there isn't any comparison sort algorithm which for an input of size $n$ can sort at least half of the permutations of the input in linear time. (For the other half the algorithm can ...
5
votes
3answers
763 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 ...
0
votes
0answers
25 views

What are some quadratic run time tasks (algorithms)? [duplicate]

Are there problems, for which best algorithms have worst run time O(input_length^2) and it is proven, that this worst time cannot be substantially improved (better algorithms do not exist). EDIT: ...
6
votes
1answer
166 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 ...
1
vote
1answer
66 views

How often can a linear speed sort succeed?

Let's say you have sorting function. It is allowed to exit with failure (but if it does not it must return a correctly sorted sequence). It is also $\mathcal O (n)$. What kind of bounds can we place ...
2
votes
1answer
79 views

Replacing n with 2n in asymptotic bounds

I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In the proof of the theorem $6$ of the paper on page 632, the authors go on ...
2
votes
1answer
196 views

How to give an upper bound on this bin packing problem?

In the bin packing with fragile objects (BPFO) problem one is given a set of objects $\{1,\ldots,n\}$ where each object $i$ has a weight $w_i$ and a fragility $f_i$ for all $i$ in the set $\{1,\ldots,...
0
votes
1answer
242 views

Estimating the number of distinct elements

Need to understand "intuition" part. It does not make sense to me why $log(d)$ is a good approximation. We have a stream $\sigma = \{a_1, ..., a_n\}$, with each $n \in [n]$, and this ...
7
votes
2answers
772 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
vote
2answers
476 views

Time complexity of comparing two $N \times N$ Matrices?

So each matrix has $N^{2}$ elements, and so just by comparing each element we would be doing $O(N^{2})$ operations. Is there any other way to compare these two matrices such that the number of ...
3
votes
1answer
352 views

How is the space hierarchy theorem different for non space constructible functions?

Sipser first introduces space constructible functions. Then uses the definition to prove the space hierarchy theorem: if f(n) is a space constructible function then there are languages that can be ...
2
votes
1answer
445 views

Regex to NFA to complement

So I've found out that a regular expression $n$ symbols long converts to an NFA with $O(n)$ states, it is linear. Now to go from that NFA to the complement of the NFA, since I can't just flip accept ...
0
votes
1answer
950 views

Prove by induction that the running time of recursive Fibonacci is exponential

This example followed from a Fibonacci algorithm in class. The professor showed us how to compute $T(n) = T(n-1) + T(n-2) + 3$, but left this step for us to prove, so I decided to attempt to prove it! ...
5
votes
1answer
119 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: ...
1
vote
1answer
656 views

Does Heapsort work in time o(n log n) in the best case?

Is it possible for Heapsort to work in time $o(n\log n)$ on certain inputs? For example in case of Insertion sort it is possible, however when it comes to Quickssort it is not possible. What about ...
2
votes
1answer
109 views

Using Context free language to simulate regular expression in finite automata

Is there a minimum number of non terminal we need to use in order to simulate a finite automata with n states? When we try to convert a language accepted by NFA to context free language, do we need n ...
2
votes
1answer
93 views

Lower bound for number of nonterminals in a CFG

Let's say we have a context-free grammar for the language $a\mbox{*}b\mbox{*}c\mbox{*}$. Is there a way to determine a lower bound for the number of nonterminals in this grammar? I'm pretty sure you ...
1
vote
1answer
846 views

Lower Bound for Comparison-based sorting algorithms

We know that the lower bound for comparison-based sorting algorithms is Ω(nlogn), where logn being the binary logarithm of n. But what about for the best-case scenario of the bubble sort, which takes ...
9
votes
1answer
774 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 ...
3
votes
2answers
109 views

Can one increment an $n$ bit integer using fewer than $2 - 2^{1-n}$ bit inspections on average?

Given an $n$-bit integer, I am interested in performing an increment operation using as few bit reads as possible. The standard binary code (standard binary representation of numbers), requires $n$ ...
1
vote
1answer
125 views

$2$-sorted array. How to sort it in minimal number of comparisons ?

It is given array $2$-sorted array $a[1..n]$. $2$-sorted denotes that $a[1]\le a[3]\le...\le$ and $a[2]\le a[4]\le ..\le$ Obviously we may split array into two sorted arrays and then merge two ...