Questions tagged [lower-bounds]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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
579 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
274 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
255 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
175 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
124 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
873 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
339 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
761 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
70 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
123 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
979 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
499 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
49 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
140 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
735 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
160 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
65 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
70 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
191 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
212 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
719 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
439 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
332 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
400 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
893 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
118 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
582 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
105 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
83 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
751 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 ...
8
votes
1answer
695 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
106 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
106 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 ...
5
votes
1answer
529 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 ...
1
vote
1answer
141 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$ ...
1
vote
1answer
145 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 ...
3
votes
2answers
870 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 ...
1
vote
0answers
192 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 ...
0
votes
1answer
282 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 ...
0
votes
1answer
66 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 (...
3
votes
1answer
1k 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 ? ...
5
votes
1answer
111 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 ...
1
vote
2answers
2k 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 ...
1
vote
1answer
38 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 ...
9
votes
2answers
299 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 ...