Skip to main content

Questions tagged [lower-bounds]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7 votes
2 answers
3k 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 ...
Igor Markov's user avatar
15 votes
4 answers
1k 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 ...
Raphael's user avatar
  • 72.6k
11 votes
1 answer
955 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 ...
user834's user avatar
  • 849
9 votes
1 answer
8k 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 ...
user5507's user avatar
  • 2,191

1 2 3 4 5
6