Questions tagged [lower-bounds]
The lower-bounds tag has no usage guidance.
208
questions
1
vote
1answer
29 views
CLRS Question 8-6 Lower bound on merging sorted lists
I'm doing the CLRS Problems and there's a part I'm having trouble following.
The question is:
Part a) Given 2n numbers, compute the number of possible ways to divide them into two sorted lists, each ...
0
votes
1answer
56 views
Decision tree and information-theoretic lower bound
Consider the following problem :
...
1
vote
1answer
77 views
Lower bound on algorithm solving certain recurrence
I have to find the lower bound of the following recursion:
$A_1 = C_1 = p_1$, $B_1 = D_1 = 1-p_1$, $F_k = A_k + B_k$. Evaluate $F_n$.
\begin{align}
A_{k+1} &= (A_k + 2C_k) p_{k+1} + (1-p_k) p_{k+1}...
0
votes
0answers
20 views
How many strings for CLOSEST STRING lower bound to apply
In the CLOSEST STRING problem, one is given (bit-)strings $s_1, \dots, s_t$, each of length $L$ and an integer $d$. The question to be answered is whether there exists a string $s$ that has hamming ...
1
vote
1answer
27 views
Hardness of boolean functions
For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$, $H_{avg}(f)$ is a function from $\mathbb{N}\longrightarrow \mathbb{N}$, termed as the average case hardness, if $\forall$ circuit $C_n$ of ...
0
votes
0answers
17 views
How to Show that an Algorithm Depends on all N inputs (and thus has a lower bound of Omega(n)) [duplicate]
In the algorithm detailed on this page: Fastest Algorithm for Computing Expected Value, I was wondering how to prove that the algorithm depends on all $n$ of the inputs it is fed (and thus has $\Omega(...
1
vote
1answer
81 views
Connection between Pseudo random generators and hardness
For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$ $H_{avg}(f)$ is defined as the largest $S(n)$ s.t. for all circuit $C_n$ of size $S(n)$, $\Pr_{x\in U_n}[C_n(x)=f(x)]<1/2+1/S(n)$. Here $...
2
votes
0answers
35 views
Is there a super-linear lower bound on the time complexity of all solutions of NP complete problems?
$P \ne NP$ would imply that any polynomial is a lower bound on the time complexity of any NP complete problem.
Is some non-trivial lower bound known at all?
1
vote
1answer
70 views
Existence of boolean function with exponential average case hardness
Show that for every large enough $n$, there is a boolean function $f\colon \{0,1\}^n\longrightarrow\{0,1\}$, whose average case hardness is exponential. The question is taken from Arora Barak ...
3
votes
1answer
29 views
Why there is no polynomially large sequence of polynomial large weights that derandomize the isolation lemma?
I was studying the paper Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size by Arvind and Mukhopadhyay and came across the following claim (Observation 1.2 on page 3):
"More ...
3
votes
1answer
1k 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 ...
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 ...
3
votes
2answers
112 views
Information-theoretic limits for a weighing puzzle
Consider the following problem:
You are given $n$ coins with labels $1, \ldots, n$. You know that coins have weights $1, \ldots, n$, but you don't know whether the labels are correct (i.e. they can ...
1
vote
2answers
84 views
Why decision tree method for lower bound on finding a minimum doesn't work
(Motivated by this question. Also I suspect that my question is a bit too broad)
We know $\Omega(n \log n)$ lower bound for sorting: we can build a decision tree where each inner node is a comparison ...
2
votes
1answer
63 views
Counting circuits with constraints
Please forgive me if this question is trivial, I couldnāt come up with an answer (nor finding one).
In order to show that there are boolean functions $f : \{0,1\}^n \rightarrow \{0,1\}$ which can be ...
1
vote
1answer
30 views
Lower bound on comparison-based sorting
I have a question from one of the exercises in CLRS.
Show that there is no comparison sort whose running time is linear for at least half
of the $n!$ inputs of length $n$. What about a fraction of $1/...
1
vote
0answers
7 views
Lower bounds for orthogonal matrix multiplication
Is it possible, according to the current state of knowledge, that orthogonal matrices can be multiplied faster than arbitrary matrices?
More precisely, let $T(N)$ denote the worst-case time of the ...
1
vote
1answer
27 views
Communication Complexity for Product Distributions
In general for the (two-party) set disjointness problem for inputs of length n, we know that the parties need to communicate $\Omega(n)$. Surprisingly, today I discovered (if I understood correctly) ...
1
vote
2answers
29 views
Algebra for min/max bounds
I am trying to model some set operations which are only well-defined if one is a subset of the other. The way the sets are constructed, I'll have a series of constraints of the form $x \subseteq y$, ...
1
vote
1answer
25 views
Lower bound time complexity for obtaining an arbitrary entry in a hashtable
I just answered this question on StackOverflow, which asks for an efficient algorithm such that given a nonempty hashtable,
the algorithm should return a pointer to an arbitrary nonempty entry in the ...
1
vote
1answer
40 views
Decision tree lower bound for finding two array elements summing to zero
I have to solve this exercise:
Given an unordered array $A[1], \ldots, A[n]$ of positive and negative integers,
determine if there are two indices $i \neq j$ such that
$A[i] + A[j] = 0$. ...
2
votes
1answer
14 views
Resolution exponential lower bound… alternative proofs?
I am reading the Resolution proof system exponential lower bound via Haken's bottleneck method for the Pigeonhole Principle as presented in Arora and Barak's Computational Complexity: A Modern ...
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 ...
1
vote
1answer
26 views
A Question related to the method of find lower bound : Trivial lower bounds
In Trivial lower bounds we just need to count the number of items in the input that needs to be processed and the number of items that need to be generated and the trivial lower bound time is then the ...
0
votes
0answers
18 views
Finding the lower bound through decision trees
One way to find the lower bound of a comparison based algorithm is to use the decision tree. U have two questions regarding this method :
1) We know that the height of the tree is path that connects ...
0
votes
2answers
126 views
Lower bound and worst case scenario
We know that the lower bound is the minimum amount of work needed to solve a problem. So for a given problem say x it has the best algorithm ( the most efficient algorithm to solve this problem ) say ...
3
votes
2answers
3k views
What is the min # of moves to sort an array from 1 to n?
Problem: You are required to sort an array with numbers from 1 to n. You can do a "move", which means choosing one element and moving it to
any place you want (insert to any place, not swap). Prove ...
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 ...
0
votes
0answers
22 views
What is an $O(n \log(n))$ binary sorting algorithm with a guaranteed low scaling constant on the run-time?
Let $O_c(f(n))$ denote that $c$ is the scaling constant for the run-time (e.g. $\text{run time} \leq c\cdot f(n) + B$ if $n$ is large enough)
The absolute lower limit on the run-time for a binary ...
0
votes
2answers
66 views
Efficiently computing minimal elements over partially ordered sets
I have a list of sets that I would like to sort into a partial order based on the subset relation.
In fact, I do not require the complete ordering, only the minimal elements.
If I am not mistaken, ...
4
votes
1answer
68 views
Conditional lower bounds on the running time of the single source shortest path problem
Just out of curiosity, I was wondering whether there is a conditional lower-bound on the running time of an algorithm for the Single Source Shortest Path Problem (on directed or undirected graphs). I ...
3
votes
1answer
52 views
Standard information-theoretic lower bound?
There should be a simple argument, but I'm struggling to see it.
Suppose Alice has a string $x \in \{0, 1\}^n$ and sends a message $s = s(x)$ to Bob. And suppose that given $s$, Bob can reconstruct ...
4
votes
1answer
112 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 ...
3
votes
2answers
144 views
Why is the lower bound for sorting strings Ī©(d + nlogn)?
I'm taking an Advanced Algorithms course. I'm currently studying efficient algorithms for sorting strings. In this chapter, it is provided a lower bound for the time complexity of $\Omega(d + n\log{n})...
1
vote
3answers
202 views
Dealing with test condition '=' for a while loop when determining a bound function/loop variant
The following is the definition of what a bound function for a while loop must satisfy:
The bound function is an integer-valued, total function of some of the inputs, variables and global data that ...
2
votes
2answers
344 views
Find both lower and upper asymptotic bounds for $T(n) = 2T(\frac{n}{2})+n^4$
So far we have learned Recursion Tree, Substitution Method, and Master's Theorem.
I'm not sure how we can find lower AND upper bounds.
I know that using Master's Theorem, we get $T(n) = \Theta(n^4)$, ...
2
votes
0answers
88 views
Decision Tree for searching an element in an n*n matrix
I just learnt decision tree concept in class. I have a question for homework. It says to prove that for searching an element in n*n matrix the lower bound is logn and prove it using decision tree.
My ...
0
votes
0answers
26 views
Minimum amount of rectangles to create a 2-dimensional matrix
From this codegolf question.
Consider an $r$ by $c$ matrix of nonnegative integers, called $M$. You also have a zero matrix of the same dimensions, called $N$. A "move" consists of replacing a ...
1
vote
1answer
47 views
Lower bound for merging $m$ sorted arrays (decision tree leaves count - permutations)
I need some help understanding how to calculate the lower bound on the time complexity of merging $m$ sorted arrays of length $n$.
The bound should be $nm \lg(m)$. I need to prove this using a ...
2
votes
0answers
25 views
Useful conditions for proving super polynomial lower bound for some kind of recurrences
Given a recurrence of the form $\forall n,m.\ \ T(n,m)=\begin{cases}1,&,m=1\\\sum_i{T(n_i,m_i)}&,\text{else}\end{cases}$
Note: both $n_i$ and $m_i$ are dependent on $n,m$ so they should have ...
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 - ...
0
votes
0answers
51 views
Number of comparisons in array where each element appears n/k times [duplicate]
Given an array of $n$ elements with $k$ distinct elements, each appearing $n/k$ times, how can I show that the number of comparisons to the sort the array in the worst case is in $\Omega(n \log k)$?
3
votes
1answer
95 views
Lower Bound for Time Complexity of Pairing Problem
Given an array X and array Y both of length n, the pairing algorithm will return the elements of the arrays matched so that the smallest element in X will be matched with the smallest element of Y, ...
3
votes
1answer
53 views
Pebble game lower bound?
This paper says pebble games have super linear lower bound for every fixed $k$ https://dl.acm.org/citation.cfm?doid=62.322433.
Why is it not considered proof of constructive example for a function in ...
1
vote
1answer
38 views
Asymptotics of a sinusoid
Consider the function
$$
f(n) = 2n^2 |\sin(\pi \cdot n/2)|.
$$
Which of the following classes does $f(n)$ belong to?
$$ O(n^2), \Omega(n^2), \Theta(n^2), \omega(n^2), o(n^2). $$
I'm working in this ...
1
vote
1answer
207 views
Comparison-based lower-bound for finding duplicates in an array of $n$ numbers
Decision Problem: Given $n$ real numbers, give an algorithm that outputs "1" iff there are at least two numbers that are identical and outputs "0" otherwise.
(Assume that comparison between any two ...
3
votes
2answers
136 views
Lower bound of disjointness by discrepancy?
I need to show that $Disc_\mu(Disj) \geq \frac{1}{2n+1}$ for any distribution $\mu: \{0,1\}^n \times \{0,1\}^n \to [0,1]$.
Disjointness is defined as
$Disj(X,Y)=\left\{ \begin{array}[ll]+1 & \...
3
votes
1answer
93 views
Why is finding minimum number of comparisons to sort $n$ elements so difficult?
In The Art of Computer Programming 2nd Ed, Vol 3, Section 5.3.1 then discuss a function $S(n)$ which is define as:
$S(n)$ : The minimum number of comparisons that suffice to sort $n$ elements.
...
3
votes
1answer
196 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 ...
3
votes
1answer
35 views
Finding maximum takes at least $\lceil n/2 \rceil$ comparisons
We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$.
I want to prove that finding the maximum in $A$ (that is, outputting the index ...
