Questions tagged [lower-bounds]
The lower-bounds tag has no usage guidance.
196
questions
1
vote
1answer
17 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
28 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
24 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
36 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$. ...
1
vote
1answer
9 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 ...
0
votes
1answer
25 views
0
votes
0answers
16 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 ...
1
vote
1answer
21 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
2answers
32 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 ...
1
vote
1answer
14 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 ...
0
votes
0answers
21 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
59 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, ...
3
votes
1answer
51 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 ...
0
votes
0answers
28 views
Is one probe to find a element is sufficient?
Let $M = \{1,2,3,\ldots,m\}$ be a a universe and $S \subseteq M$ denotes the number of elements comes from $M$ which we want to store such that query of the type "Is $x \in S$"?Let $n$ denotes the ...
4
votes
1answer
90 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
112 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})...
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 ...
2
votes
2answers
208 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
86 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 ...
0
votes
0answers
16 views
Given we restrict the time and memory allowed what bounds can we place on a halting decider?
If a program is given as much memory and as much time to execute as it wants, then the halting problem is undecidable, and by Rice's theroem all non-trivial, semantic properties of programs like that ...
1
vote
1answer
31 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 ...
1
vote
0answers
22 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 ...
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
81 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
52 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
3answers
151 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 ...
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
154 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
96 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
90 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
34 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 ...
3
votes
1answer
3k 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 ...
2
votes
1answer
119 views
What is Ironic complexity? What are some good resources to learn about it?
The term "Ironic complexity" was coined by Scott Aaronson for the stuff Ryan Williams does in the area of complexity theory. Could anyone tell me what kind of problems and approaches does Ryan ...
0
votes
0answers
66 views
Postive interval problem lower bound
I was trying to solve the question given below.
Algorithm :
Using divide and conquer technique, divide the input till we get a very small size array's ( let us say of size 2 ). Solve these small ...
-1
votes
2answers
109 views
Why do you need at least ln(n!) many comparison to sort a list?
"If every element comparison (testing whether $a_i \le a_j$ ) provides at most one bit of information, argue that you need at least on the order of $\ln(n!)$ many tests/comparisons to sort the list."
...
0
votes
1answer
110 views
Do you >have< to define the upper and lower bound? (context: traveling salesman)
Do one have to define the upper and lower bound to be able to solve the tsp, or is that just an unnecessary intermediate step? And if so, why would one define those bounds? (context: the traveling ...
1
vote
2answers
188 views
Why are greedy algorithms used to find upper/lower bounds? (when they doesn't guarantee an optimal solution)
Take the nearest neighbor algorithm for the traveling salesman problem as an example. Why is it used to find the upper bound? When can't it guarantee an optimal solution?
(Thanks to many comments ...
6
votes
1answer
247 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?
2
votes
1answer
141 views
Using Yao's principle to find a lower bound
This is a HW question, so I'm not expecting any answers, just a general guidance/help.
Definition. Given $\underset{\neq0}{\underbrace{s}}\in\left\{ 0,1\right\} ^{n}$, a function $f:\left\{ 0,1\right\...
0
votes
1answer
40 views
Showing $2^x$ is a lower bound
How do I show that $2^x - x^2 \in \Omega(2^x)$?
Basically, I know that this means that $\exists a, x_0 \in \mathbb{R^+}, \forall x \in \mathbb{N}, a.2^x \leq 2^x - x^2$.
I worked around a bit with ...
1
vote
2answers
100 views
findMax reduce to sort
Can I reduce the find max (or find min) problem to the sort problem? Because if so, knowing the lower bound for find max is Ī©(n) I can also infer that the lower bound for sorting is Ī©(n) too?
I'm ...
1
vote
1answer
235 views
lower bound proof with adversary argument
We have to run a song on a Walkman, for that we need 2 full batteries. Let's say we have a mixed set of 30 batteries (15 are empty and and 15 are full) and then only way to test if the battery is full ...
2
votes
0answers
30 views
Query complexity of exact learning and combinatorial parameter
When defining the query complexity of exact learning for a concept $c$ (considered as a function from $\{0,1\}^n \mapsto \{0,1\}$) in a concept class $\mathcal{C}$, we often come across the following ...
2
votes
1answer
86 views
Minimum and maximum of sum of inverse degree of a graph
Suppose we have a simple undirected graph $G(V,E)$, where $V$ and $E$ are the set of vertices and edges respectively. we denote $d(v)$ as the degree of a vertex $v \in V$. I am interested to find ...
2
votes
0answers
69 views
Highest lower bound on an NP complete problem
What is the highest time complexity lower bound that has been proven on any (non-contrived) NP complete problem?
2
votes
1answer
326 views
Correctness of lower bound proof
I am working on this exercise with the purpose of learning how to provide proper proofs and I would like to know if my proof for the following problem is correct.
Given a sorted array $A$ (of $n$ ...
1
vote
1answer
118 views
Proof of Lower Bound for Deterministic Distinct Elements Algorithm
There is a proof in this document (page 8, Section 4, Lemma 3: https://inst.eecs.berkeley.edu/~cs170/fa16/lecture-11-29.pdf) that mirrors a proof my professor gave in my algorithms class. The lemma ...
0
votes
1answer
30 views
Use substitute algorithm to prove T(n) =4T(n/2) + n^2 compact lower bound [duplicate]
how to use substitute algorithm to prove T(n) =4T(n/2) + n^2 compact lower bound.
this is a algorithm of my class home work,but i dont know how to solve it.
3
votes
0answers
96 views
How hard is APPROXIMATE-#SAT? [closed]
It is well known that the problem of counting the satisfying assignments of SAT, namely the problem #SAT, is #P-complete.
It is also suspected (somewhat less widely) that even deciding SAT should ...
