Questions tagged [lower-bounds]
The lower-bounds tag has no usage guidance.
177
questions
1
vote
1answer
15 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
20 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
49 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
38 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
42 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
40 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
35 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
32 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
71 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
71 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
31 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 ...
2
votes
1answer
325 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
60 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
27 views
Dynamic Perfect Hashing and Lower Bound
I am writing a Seminar about dynamic perfect hashing and its lower bound by the FKS schema using the the adversary method mentioned here by using a Tree data structure. But somehow i don t get how ...
0
votes
0answers
64 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
87 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
67 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
120 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
213 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?
1
vote
0answers
21 views
Complexity class without fixed-poly size circuit
$PP$ is shown to have no fixed-poly size circuit by Vinodchandran.
Bounded inside the polynomial hierarchy, $\Sigma^2_p$ is also shown to possess no fixed-poly size circuit by Kannan.
In notation, ...
2
votes
1answer
105 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
27 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
49 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
162 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
29 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 ...
1
vote
1answer
59 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
57 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
223 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
70 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
23 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
84 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 ...
0
votes
1answer
121 views
Is this lower bound proof for the comparison-based sorting problem correct?
Here is a lower bound proof for the comparison-based sorting problem:
Any comparison-based sorting algorithm can be considered to work by putting elements into their final positions one by one (Take ...
2
votes
1answer
76 views
How to prove that a problem can't be solved in time $\mathcal O(n^{1/2 - \epsilon})$?
I have seen many problems in graph theory and in other related fields which admit a sublinear (in input size) running time $\mathcal O(n^{1/2})$ algorithm, where $n$ is the input size. I am not sure ...
0
votes
0answers
168 views
How to find lower bound of f(n) for master theorem
I'm studying the master method to solving a recurrence. It describes three cases, the last one of which depends on what lower bound a function f(n) has.
I usually ...
2
votes
0answers
38 views
From SETH to circuit lowerbounds
Are there reductions from SETH (Strong Exponential Time Hypothesis) to lowerbounds against threshold circuits? (maybe for computing Boolean functions of the form OR-of-AND-of-OR)
In threshold ...
1
vote
2answers
777 views
Is it possible to solve 3SUM in $O(n^2)$ time?
Problem: 3SUM
Input: Three lists A, B and C of integers and an integer k. Each list contain $n$ numbers.
Task: Decide whether there exists a tuple (a, b, c) ∈ A × B × C such that a + b + c = k.
...
0
votes
0answers
29 views
Circuit Lower bound for $EXP^{NP}$
By Burhman, Fortnow and Thierauf result Paper Link, we know that $MA_{EXP} \not\subset P/poly$.
Also, we know that $MA \subseteq P^{NP}$ (or $\Delta_{2}^{P}$ in some literatures).
By using the ...
2
votes
1answer
77 views
Tight bound on the number of intersections between a line and a triangulation
I'm interested in the maximum number of intersections that a line and a triangulation on $n$ points could have. More specifically, given $n$, we are interested in the worst-case (maximum) number of ...
18
votes
2answers
3k views
How to prove that matrix multiplication of two 2x2 matrices can't be done in less than 7 multiplications?
In Strassen's matrix multiplication, we state one strange ( at least to me) fact that matrix multiplication of two 2 x 2 takes 7 multiplication.
Question : How to prove that it is impossible to ...
4
votes
4answers
567 views
Is $Ω(n\log n)$ the lower-bound for *all* sorting algorithms or *just comparison-based* sorting algorithms?
Is $Ω(n\log n)$ the lower-bound for all sorting algorithms or just comparison-based sorting algorithms?
If the latter, is it possible for there to be general-purpose sorting algorithms which perform ...
2
votes
1answer
107 views
“Natural” reductions vs “Polynomial-time many-one” reductions (Karp Reductions)
For two problems $A$ and $B$ and a Karp Reduction $R$ from $A$ to $B$, we call the reduction $R$ natural if, for any instance $I$ of problem $A$, the size of $R(I)$ (as well as the possible numerical ...
0
votes
1answer
518 views
How to prove that matrix inversion is at least as hard as matrix multiplication?
Suppose we are given a matrix $A$ over real numbers and we want to computer the inverse of matrix $A$. There are various algorithms to do so and it also turn out that we can use matrix multiplication ...
0
votes
1answer
94 views
Find a subset in constant many queries
Black box of $f(x)$ means I can evaluate the polynomial $f(x)$ at any point.
Input: A black box of monic polynomial $f(x) \in\mathbb{S}[x]$ of degree $d$.
Question : $\mathbb{S} \subseteq \mathbb{Z}$,...
1
vote
1answer
4k views
how to find upper bound and lower bound of quadratic equation
I am relatively new to algorithms, I wrote one pattern matching algorithm and its running time is $O(n^2)$, I tried it by step count method, direct method and also the constant method which all yields ...
1
vote
1answer
329 views
Best Algorithm for searching for an index in an array such that A[i] = i
Recently i got a question in one of my exams about asking for an algorithm which searches an element in a sorted array such that $A[i] = i$. My algorithm was based on binary search and did a $O (\log ...
1
vote
0answers
200 views
Reductions: Lower Bound and Upper Bound
The question is from my complexity-theory course.
Explain the concept of polynomial reduction between problems and explain how, and under what circumstances, lower bound and upper bound problems can ...
1
vote
1answer
82 views
Lower bounds: Detecting a length 2 path
Prove that determining if a non-directed graph of $n$ vertices has or doesn't have a length $2$ path requires time $\Omega(n^2)$, assuming that the graph is represented as an adjacency matrix.
3
votes
1answer
104 views
Proving that converting min-heaps to max-heaps requires time Ω(n)
Suppose I have a min-heap SH stored inside an array. I can perform the operations:
view-min(SH) in $O(1)$
extract-min(SH) in $O(\log n)$
insert(SH) in $O(\log n)$
is-empty(SH) in $O(1)$
If I want to ...
1
vote
1answer
298 views
Doubt regarding address calculation in two-dimensional arrays
I am reading about the address calculation formulas for one and two-dimensional arrays. I have two related doubts concerning it.
In one of the problems, we are asked to calculate the ...
1
vote
1answer
153 views
Lower bound on space of DFS keeping the running time linear
$\mathsf{DFS(G, u) \text{}}$, $G = (V,E)$
Input : A Directed graph $G$ and a source vertex $u$.
Find : Is $v$ reachable from vertex $u$ for all $v \in V$ ?
Model of computation : Word RAM , one ...
