Questions tagged [lower-bounds]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
706 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
68 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
122 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
974 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
476 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
163 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
47 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
125 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
719 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
156 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
63 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
190 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
191 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
691 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
424 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
327 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
380 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
878 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
534 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
102 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
79 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
710 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
676 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
99 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
90 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
517 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
131 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
140 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
850 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
186 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
277 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
63 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
105 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
290 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
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 ...
3
votes
3answers
3k 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
2answers
267 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 ...
5
votes
2answers
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, ...
6
votes
1answer
566 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 ...
3
votes
1answer
197 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 ...
6
votes
1answer
206 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 ...
-2
votes
1answer
315 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.