2022 Developer Survey is open! Take survey.

New answers tagged

0 votes

How to show that the median cannot be maintained in $O(1)$ time?

The question's title presupposes the wrong answer. Median can in fact be maintained in $O(1)$ time. Here is the counter example disproving the title's fallacious claim of “How to show that the ...
user avatar
11 votes
Accepted

How to show that the median cannot be maintained in $O(1)$ time?

If you can maintain the median of $n$ objects in $O(1)$, then you can sort a sequence $x_1, \dots, x_n$ in $O(n)$: first you compute a value $a$ smaller than all elements in the sequence and a value $...
user avatar
  • 685
2 votes
Accepted

Maximize a special monotone submodular function - is it easier?

I believe that the problem is NP-Hard and it admits a FPTAS. Let me sketch my thoughts. NP-Hardness: Consider a slight variant of the well-known 2-Partition problem. Given $2n$ non-negative integers $...
user avatar

Top 50 recent answers are included