The lower-bounds tag has no wiki summary.
2
votes
1answer
48 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
3answers
217 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 ...
3
votes
1answer
42 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 ...
10
votes
1answer
120 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 = ...
3
votes
1answer
58 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? ...
4
votes
2answers
69 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
79 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 ...
9
votes
0answers
123 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 ...
4
votes
1answer
92 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
90 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
72 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
39 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
69 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 < ...
4
votes
2answers
132 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
62 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$ ...
6
votes
1answer
133 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 ...
1
vote
1answer
113 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 ...
4
votes
2answers
194 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 ...
12
votes
4answers
410 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 ...
5
votes
1answer
120 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 ...
5
votes
1answer
263 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 ...
