Questions tagged [lower-bounds]
The lower-bounds tag has no usage guidance.
241
questions
0
votes
1
answer
279
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 ...
- 109
7
votes
2
answers
1k
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,188
1
vote
1
answer
642
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 ...
- 165
3
votes
1
answer
380
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,923
2
votes
1
answer
516
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 ...
- 383
0
votes
1
answer
1k
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
1
answer
130
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:
...
- 2,624
1
vote
1
answer
800
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 ...
- 553
2
votes
1
answer
113
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 ...
- 61
2
votes
1
answer
112
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 ...
- 123
1
vote
1
answer
966
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 ...
- 113
9
votes
1
answer
869
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 ...
- 619
3
votes
2
answers
115
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,103
1
vote
1
answer
170
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 ...
- 553
5
votes
1
answer
664
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 ...
- 11k
1
vote
1
answer
160
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$ ...
- 553
1
vote
1
answer
159
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 ...
- 553
3
votes
2
answers
984
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 ...
- 553
1
vote
0
answers
211
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 ...
- 11
0
votes
1
answer
327
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 ...
- 103
0
votes
1
answer
90
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 (...
- 553
4
votes
2
answers
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 ?
...
- 553
5
votes
1
answer
150
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 ...
- 506
1
vote
2
answers
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 ...
- 13
1
vote
1
answer
47
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 ...
- 127
9
votes
2
answers
376
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 ...
24
votes
5
answers
47k
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 ...
- 738
3
votes
3
answers
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?
2
votes
2
answers
427
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 ...
- 21
5
votes
2
answers
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, ...
- 161
6
votes
1
answer
912
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 ...
user23522
3
votes
1
answer
270
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 ...
- 9,441
6
votes
1
answer
277
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 ...
- 1,105
-2
votes
1
answer
436
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.
9
votes
2
answers
792
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 ...
- 12.5k
5
votes
1
answer
487
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 ...
- 860
8
votes
1
answer
634
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 ...
- 299
6
votes
1
answer
872
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 ...
- 162
1
vote
1
answer
54
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 ...
- 2,862
2
votes
2
answers
860
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 ...
- 163
25
votes
3
answers
8k
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 ...
- 713
9
votes
4
answers
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 ...
D.W.♦
- 152k
1
vote
1
answer
72
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 ...
- 860
6
votes
1
answer
119
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 ...
user27145
1
vote
1
answer
75
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 ...
- 113
0
votes
1
answer
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 ...
2
votes
1
answer
406
views
What is the lower bound for finding the third largest in a set of $n$ distinct elements?
What is the lower bound for finding the third largest in a set of $n$ distinct elements?
For the case of finding the second largest, we have the tight lower bound of $n + \lceil \lg n \...
- 9,441
3
votes
1
answer
100
views
Understanding the flaw in a proof attempt of the Communication Complexity of Equality
I'm new to communication theory and I've been wondering where the following simple argument fails:
Equality Problem
We have two players, player 1 Alice who gets an $n$-bit vector $X$ and player 2 Bob ...
- 31
21
votes
2
answers
662
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 - ...
- 2,624
4
votes
1
answer
515
views
Lower space bound on a turing machine accepting palindromes
Let
$$
PAL = \lbrace x \in \lbrace 0, 1, \# \rbrace^* | x = rev(x) \rbrace
$$
How do I show that a turing machine deciding $PAL$ must use space $\Omega(\log n)$?
I have a feeling that I need to use ...
- 51