Timeline for Counting elements that are greater than the median of medians
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 9, 2014 at 20:37 | comment | added | Massimo Cafaro | Sure, I fully agree. | |
| Jan 9, 2014 at 0:16 | comment | added | Carl G | If you put $-3$ after the parenthesis, that is the same as putting $-1$ inside the parentheses. I think we agree that the number subtracted inside the parentheses is the number of groups completely discarded. But we don't want to discard the median-of-medians' group entirely. | |
| Jan 8, 2014 at 20:48 | comment | added | Massimo Cafaro | Sure, but I said that you must subtract -3 to the expression just $after$ the parenthesis, so that you are subtracting 3 elements which are $less$ than the median of medians for that group and this is correct because you are computing the number of elements that are greater than the median of medians. You also subtract additional 2 elements related to the leftovers group for a total of 5. | |
| Jan 8, 2014 at 17:26 | comment | added | Carl G | Right, but the two elements less than the median-of-medians are not accounted for in the first place. (The two elements less than any median are not accounted in any group.) The $3$ at the beginning is '3 elements per group (groups that will have elements greater than the median-of-medians), i.e. the median of that group and the two elements greater than the median of that group.' | |
| Jan 8, 2014 at 8:55 | comment | added | Massimo Cafaro | Remember that, by assumption, all of the elements are distinct. That means that in the group of the median of medians, only two elements are greater than the median of medians since the median of median can not be greater than itself! Therefore, you must remove 3 elements, including the median of medians, that are less than the median of medians from that group, not one. | |
| Jan 7, 2014 at 22:09 | vote | accept | Carl G | ||
| Jan 7, 2014 at 22:08 | comment | added | Carl G | I'm not sure that your analysis of the elements is completely correct, though. The quantity $3(\ldots)$ is three elements per group: 1 median plus 2 elements greater than the median. One of these groups contains the median-of-medians, and so you would subtract 1 to remove the median-of-medians, not 3, from it. If you subtract 3, you also remove the two elements in the median-of-medians' group that are actually greater than the median-of-medians. I agree that at most we remove 2 elements from leftovers. So if I am correct, now it is $-1$ inside the parentheses. Thanks! | |
| Jan 7, 2014 at 21:42 | comment | added | Carl G | "2 is the number of groups we are discarding" okay yes I understand that now. | |
| Jan 7, 2014 at 19:33 | history | edited | Massimo Cafaro | CC BY-SA 3.0 |
added 28 characters in body
|
| Jan 7, 2014 at 19:27 | history | edited | Massimo Cafaro | CC BY-SA 3.0 |
added 28 characters in body
|
| Jan 7, 2014 at 19:22 | history | edited | Massimo Cafaro | CC BY-SA 3.0 |
deleted 19 characters in body
|
| Jan 7, 2014 at 19:16 | history | edited | Massimo Cafaro | CC BY-SA 3.0 |
added 162 characters in body
|
| Jan 7, 2014 at 18:56 | history | edited | Massimo Cafaro | CC BY-SA 3.0 |
deleted 10 characters in body
|
| Jan 7, 2014 at 18:36 | history | answered | Massimo Cafaro | CC BY-SA 3.0 |