7
$\begingroup$

The paper Stable Minimum Space Partitioning in Linear Time describes an algorithm that stably sorts a binary array (an array whose elements can only have two distinct values) in $O(n)$ time complexity and $O(1)$ space complexity. After reading the paper, I am not really convinced that the algorithm described is actually $O(1)$ space complexity which is one of the main selling points of the algorithm that distinguishes it from other partitioning algorithms.

Although the algorithm uses constant memory (technically it is $O(\log n)$ bits, but we can consider it $O(1)$ in practical use), it doesn't use $O(1)$ counters. The authors define $O(1)$ space as "we assume that a constant number of extra storage locations, each capable for storing a word of $O(\log_2 n)$ bits, is available" (page 2). But later in algorithm D, the authors clearly use $O(\log(n)/\log(\log(n)))$ counters thereby contradicting their earlier statement of $O(1)$ space complexity.

The reason why having a constant number of counters is important is that, without it, the algorithm most probably wouldn't work out that well in practical use. The algorithm can only have $O(\log_2 n)$ extra space if we use a variable number of integer counters that are of variable size. The only way we can have a variable number of integer counters of variable size is if we dynamically allocate them and that would drastically slow down the algorithm, hence making the algorithm impractical.

Is the algorithm indeed not $O(1)$ space complexity, or am I misunderstanding the paper somehow?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

There is no problem here. The paper (which I was led to by your question) could have been worded better, but the $O(\log n / \log \log n)$ counters use $O(\log \log n)$ bits each as they are used to sort an array of $O(\log n)$ elements.

Their algorithm is not really meant for ordinary practical use: The $O(1)$ space requirement leads to a poor constant factor here.

Their algorithm is quite complicated. The question Linear time in-place stable sort (which uses $O(\log n)$ bit integer keys instead of just 0 or 1) might help you with the fuller picture.

$\endgroup$
3
  • $\begingroup$ The authors define O(1) space as "we assume that a constant number of extra storage locations, each capable for storing a word of O(log2n) bits, is available". O(log n / log log n) counters is still clearly not a constant number of counters. $\endgroup$
    – Mathphile
    Aug 20, 2022 at 22:58
  • $\begingroup$ I guess this further leads to the question: Does an algorithm exist that can stably sort a binary array in O(n) time and O(1) space with a constant number of storage locations? $\endgroup$
    – Mathphile
    Aug 20, 2022 at 23:07
  • $\begingroup$ @Mathphile But they do use a constant number of storage locations: The extra counters are emulated using those locations and bit shift operations. $\endgroup$ Aug 22, 2022 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.