Timeline for duplicate detection problem
Current License: CC BY-SA 2.5
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2017 at 12:37 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| Jul 17, 2012 at 22:16 | comment | added | Zsbán Ambrus | Shouldn't this question go to cstheory.stackexchange.com ? | |
| Jul 16, 2012 at 22:59 | answer | added | Simd | timeline score: 5 | |
| Jun 2, 2010 at 18:27 | comment | added | David E Speyer | Stupid observation: with only O(1) space, you can't actually address the whole array. So you probably want something like "O(1) space, but pointers count as constant space." | |
| Jun 1, 2010 at 16:36 | vote | accept | Jason S | ||
| May 20, 2010 at 23:37 | answer | added | Ryan Williams | timeline score: 8 | |
| May 20, 2010 at 20:54 | answer | added | leonbloy | timeline score: 0 | |
| May 20, 2010 at 20:53 | comment | added | Jason S | ok, interesting.... | |
| May 20, 2010 at 20:50 | comment | added | David Eppstein | By small I meant polynomially bounded in the input size. Integers in the range 1..n can be sorted by bucket sort in linear time and integers in the range 1..polynomial can be sorted by radix sort in linear time. It's not a question of what's realistically large, it's a question of whether you allow your inputs to be used as array indexes or you artificially pretend your computer can only access them via pairwise comparisons. | |
| May 20, 2010 at 20:27 | answer | added | Gerhard Paseman | timeline score: 0 | |
| May 20, 2010 at 18:18 | comment | added | Jason S | Clarification: Sorting is the O(n log n) solution only if modifying the array is allowable, which is not the case, so yes, technically it's not a solution. "sorted in O(n) time anyway because it's all small integers" -- that's not part of the problem statement. Comp sci folks tend to assume large in the sense of realistically large (e.g. N = in the 10<sup>3</sup> - 10<sup>9</sup> range)... not unbounded but still important for computing time estimates. | |
| May 20, 2010 at 17:26 | comment | added | David Eppstein | Sorting is not an O(n log n) solution, because it uses much more than O(1) space and/or modifies the array. And this input could be sorted in O(n) time anyway because it's all small integers. | |
| May 20, 2010 at 17:24 | comment | added | Jason S | Reasonable assumptions are probably that elements of arrays/memory of size N are reachable in O(1) time, that addition/multiplication/subtraction/division of quantities of N or N<sup>2</sup> are operations in O(1) time. The stackoverflow discussion talked about computing the product of the array's elements, but arbitrary-precision computation of quantities in the range of N! is probably unreasonable without accounting for using large numbers. | |
| May 20, 2010 at 17:19 | history | edited | Jason S | CC BY-SA 2.5 |
added 135 characters in body
|
| May 20, 2010 at 17:17 | comment | added | Jason S | yes. the sort-and-look-for-duplicates approach is the easy O(N log N) solution. | |
| May 20, 2010 at 16:05 | answer | added | David Eppstein | timeline score: 16 | |
| May 20, 2010 at 15:58 | comment | added | fedja | It is quite often assumed that if you have an input of size $N$ on a RAM then, you are allowed standard operations on registers of length $O(\log N)$ in unit time. Apparently, this is what was meant here. | |
| May 20, 2010 at 15:18 | comment | added | Roland Bacher | So you want this to be faster than sorting (which can be done in $O(N\mathrm{log}(N))$ steps if I am not mistaken)? | |
| May 20, 2010 at 15:09 | comment | added | Noah Stein | What is your model of computation? Such an array (and in particular such a permutation) takes $\mathcal{O}(N\log N)$ space to store, so it would take that much time just to read it. | |
| May 20, 2010 at 14:51 | history | asked | Jason S | CC BY-SA 2.5 |