Timeline for finding the parity of a permutation in little space
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 14, 2011 at 18:48 | comment | added | Igor Rivin | @A.Rex. Touche, see the edit. | |
| Aug 14, 2011 at 18:47 | history | edited | Igor Rivin | CC BY-SA 3.0 |
changed the sorting algorithm
|
| Aug 13, 2011 at 15:34 | comment | added | aorq | @Igor: In addition to the problems that others have mentioned, quicksort is NOT in-place in the sense that it uses $O(1)$ extra bits, or even $O(1)$ extra words. It requires expected $O(\log^2 n)$ extra space. You have to keep track of a call stack that's logarithmically deep and has a couple indices per call, which is logarithmically many bits. | |
| Aug 12, 2011 at 10:39 | comment | added | Emil Jeřábek | @Igor: Yes, that’s what I meant. After a cycle is accounted for, we no longer need to know how it was structured, so we can as well overwrite it with check marks. | |
| Aug 11, 2011 at 21:49 | comment | added | Igor Rivin | Actually, I take my last comment to @Emil back -- he presumably meant that you can overwrite the entry of the array by the mark. | |
| Aug 11, 2011 at 18:58 | comment | added | Igor Rivin | @Gerhard: very true. @Emil: not very true: you need space to mark the elements. | |
| Aug 11, 2011 at 18:11 | comment | added | Gerhard Paseman | If you get to modify the array, you can do it in O(n) steps by swapping the contents of locations i and pi(i), increasing i whenever a fixed point is encountered. Gerhard "Ask Me About System Design" Paseman, 2011.08.11 | |
| Aug 11, 2011 at 17:50 | comment | added | Emil Jeřábek | If you allow that, and ignore the size of indices (as you also did above), then Brendan’s original algorithm (trace each cycle while marking its elements) would also run in space $O(1)$, since you can mark the elements in-place. | |
| Aug 11, 2011 at 17:42 | comment | added | Igor Rivin | I think that depends on who you talk to. For algorithms people, "space complexity $O(f(x))$ means that you are using $O(f(x))$ scratch space. | |
| Aug 11, 2011 at 16:32 | comment | added | Emil Jeřábek | That's not how space complexity is defined. If you modify the input tape, you have to include it in the space bound. | |
| Aug 11, 2011 at 16:14 | comment | added | Igor Rivin | Quick sort is an in-place algorithm -- the additional space is something like one cell. | |
| Aug 11, 2011 at 15:47 | comment | added | Emil Jeřábek | How do you intend to implement quick sort in space smaller than $n$? | |
| Aug 11, 2011 at 15:24 | history | answered | Igor Rivin | CC BY-SA 3.0 |