Questions tagged [lower-bounds]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
18
votes
1answer
251 views

guillotine cuts versus general cuts

Cutting problems are problems where a certain large object should be cut to several small objects. For example, imagine you have a factory that works with large sheets of raw glass, of width $W$ and ...
3
votes
1answer
907 views

How to analyze the lower bound of the horse racing problem using adversary argument?

Consider the following problem: Give an algorithm to find the $1^{st}, 2^{nd}, 3^{th}$ fastest horses from 25 horses. In each round, at most 5 horses can race and you can get the exact position of ...
7
votes
2answers
2k views

Can you do an in-place reversal of a string on a vanilla turing machine in time $o(n^2)$?

By a vanilla Turing machine, I mean a Turing machine with one tape (no special input or output tapes). The problem is as follows: the tape is initially empty, other than a string of $n$ $1$s and $0$s ...
4
votes
1answer
1k views

Lower-bound complexities for finding common elements between two unsorted arrays

I'm facing some problems that deal with finding common elements between unsorted arrays and I'd like to know whether there are well-known lower-bounds for the worst-case and, eventually, what are ...
2
votes
1answer
5k views

Time complexity in Big O notation for Harmonic series with first k terms missing

Firstly, let's suppose there exists an algorithm where $i$ iterates from $1$ to $n$, spending $\frac{n^2}{i}$ time in each iteration. Thanks to the well known $O(\log n)$ upper bound for the Harmonic ...
2
votes
2answers
1k views

A Problem on Time Complexity of Algorithms

For every integer $t$, is there a problem whose solutions can be verified in $O(n^{s})$ time but cannot be found in $O(n^{st})$ time? By verifying, I mean that given a candidate solution $y$, we can ...
5
votes
1answer
857 views

Lower bound for sorting n arrays of size k each

Given $n$ arrays of size $k$ each, we want to show that at least $\Omega(nk \log k)$ comparisons are needed to sort all arrays (indepentent of each other). My proof is a simple modification of the ...
21
votes
1answer
532 views

Is detecting "doubly" arithmetic progressions 3SUM-hard?

This is inspired by an interview question. We are given an array of integers $a_1, \dots, a_n$ and have to determine if there are distinct $i \lt j \lt k$ such that $a_k - a_j = a_j - a_i$ $k - j = ...
4
votes
1answer
2k views

Complexity of transposing matrices represented as list of row or column vectors

Given [[1,4,7],[2,5,8],[3,6,9]] which is a list of the column vectors of matrix |1, 2, 3| |4, 5, 6| |7, 8, 9| is $ \Omega(n^2) $ a lower bound for transposing? ...
5
votes
2answers
181 views

Constraint violation and efficiency in search

It seems that (in a broad sense) two approaches can be utilized to produce an algorithm for solving various optimization problems: Start with a feasible solution and expand search until constraints ...
3
votes
2answers
2k views

Methods for Finding Asymptotic Lower Bounds

I've found in many exercises where I'm asked to show that $f(n)=\Theta(g(n))$ where the two functions are of the same order of magnitude I have difficulty finding a constant $c$ and a value $n_0$ for ...
10
votes
0answers
244 views

Is there a data-structure which is more efficient than both arrays and linked lists? [duplicate]

Background: In this question we care only about worst-case running-time. Array and (doubly) linked lists can be used to keep a list of items and implement the vector abstract data type. Consider the ...
5
votes
1answer
228 views

Simple lower bounds against AC0

It is known that $Parity \notin AC^0$ (nonuniform), but the proof is rather involved and combinatorial. Are there simpler, but weaker lower bounds, say for $NP \not \subseteq AC^0$ or $NEXP \not \...
1
vote
3answers
279 views

Search spaces and computation time

This question follows on previous questions (1), (2), where we define an initial space of possibilities and reason about how a solution is chosen from that. Consider a problem P where we are given: ...
1
vote
1answer
789 views

Input that causes an operation on a binomial heap to run in $\Omega(\log n)$ time?

I was studying binomial heaps and its time analysis. Are there any inputs that cause DELETE-MIN, DECREASE-KEY, and DELETE to run in $\Omega(\log n)$ time for a binomial heap rather than $O(\log n)$?
1
vote
1answer
75 views

Progress of algorithms in problem spaces

Continuing in the vein of two prior questions (1) and (2), we started with sorting, where we had a set of $n!$ input possibilities a goal space of only one element consisting of the one correct ...
3
votes
2answers
112 views

Lower bound on size of proof that a list of integers is sorted

Suppose we have a list of unbounded integers, written in binary, and we want to write a (formal) proof that the list is sorted in ascending order. Such a proof might look (informally) like: "2 < 3,...
6
votes
2answers
2k views

Space complexity below $\log\log$

Show that for $l(n) = \log \log n$, it holds that $\text{DSPACE}(o(l)) = \text{DSPACE}(O(1))$. It's well known fact in Space Complexity, but how to show it explicitly?
4
votes
1answer
103 views

Proofs based on narrowing down sets of possibilities

Consider the argument made in this question based on the comparison sorting lower-bounds proof, which runs as follows. First, the comparison sorting lower-bounds proof was recited: For $n$ distinct ...
8
votes
2answers
235 views

Is there any nontrivial problem in the theory of serial algorithms with a nontrivial polynomial lower bound of $\Omega(n^2)$?

In the theory of distributed algorithms, there are problems with lower bounds, as $\Omega(n^2)$, that are "big" (I mean, bigger than $\Omega(n\log n)$), and nontrivial. I wonder if are there problems ...
6
votes
1answer
879 views

Generalizing the Comparison Sorting Lower Bound Proof

Let's start with the comparison sorting lower bound proof, which I'll summarize as follows: For $n$ distinct numbers, there are $n!$ possible orderings. There is only one correct sorted sequence of ...
7
votes
1answer
3k views

Lower bound for Convex hull

By making use of the fact that sorting $n$ numbers requires $\Omega(n \log n)$ steps for any optimal algorithm (which uses 'comparison' for sorting), how can I prove that finding the convex-hull of $...
6
votes
2answers
2k views

Lower bounds: queues that return their min elements in $O(1)$ time

First, consider this simple problem --- design a data structure of comparable elements that behaves just like a stack (in particular, push(), pop() and top() take constant time), but can also return ...
14
votes
4answers
888 views

Is every linear-time algorithm a streaming algorithm?

Over at this question about inversion counting, I found a paper that proves a lower bound on space complexity for all (exact) streaming algorithms. I have claimed that this bound extends to all linear ...
11
votes
1answer
835 views

Bound on space for selection algorithm?

There is a well known worst case $O(n)$ selection algorithm to find the $k$'th largest element in an array of integers. It uses a median-of-medians approach to find a good enough pivot, partitions ...
9
votes
1answer
7k views

How to use adversary arguments for selection and insertion sort?

I was asked to find the adversary arguments necessary for finding the lower bounds for selection and insertion sort. I could not find a reference to it anywhere. I have some doubts regarding this. I ...

1 2 3 4
5