1
$\begingroup$

As recursive algorithms depend on the stack whose size is in almost all the cases depend on input, why don't we consider all the recursive algorithms as NOT-inplace algorithms?

Consider for example, Quicksort, we say it as inplace sort, but in reality, (average case) it uses O(log(n)) memory in stack? So, how can it be called inplace sort?!

$\endgroup$

migrated from stackoverflow.com Jan 2 '12 at 12:58

This question came from our site for professional and enthusiast programmers.

  • 30
    $\begingroup$ @AlanTuring: Could you please consider choosing a less questionable user name? $\endgroup$ – Jukka Suomela Jan 3 '12 at 21:58
  • 2
    $\begingroup$ I think the intuition about in-place sorting might be not about the auxiliary memory, it is about using only $O(1)$ extra data cells to store the members of the array being sorted. Maybe you should fist define (or ask) what is an in-place sorting algorithm? $\endgroup$ – Kaveh Jan 3 '12 at 23:03
  • 4
    $\begingroup$ @Jukka Suomela, Why Alan Turing is questionable?! I admire him like many here! $\endgroup$ – Alan Turing Jan 4 '12 at 1:37
  • 8
    $\begingroup$ I think by "questionable", @JukkaSuomela means "presumptuous". $\endgroup$ – Jeffε Jan 4 '12 at 21:01
  • 7
    $\begingroup$ the common practice here is to use our real names. also, unless you think anything you will post here will be worthy of being signed by Alan Turing, I would change the name $\endgroup$ – Sasho Nikolov Jan 5 '12 at 0:58
12
$\begingroup$

Recursion is an abstract concept. Talking about whether or not it has in-place semantics is nonsense. (Unless of course the language specifies recursion semantics.) This idea is related to how it is nonsense to talk about the speed of a language.

How recursion is implemented is another question. For example, a compiler might perform tail call optimization where recursion can be converted to a loop under the hood among other things. In this case, recursion maintains constant stack space (assuming your architechure uses stacks :D)

EDIT: What does this all mean? It means that there exist recursive algorithms that are in-place when implemented in certain fashions. Thus the statement "All recursive algorithms are inherently not in-place" is false.

$\endgroup$
  • 4
    $\begingroup$ There's nothing nonsensical about considering space usage for abstract recursive algorithms. Recursion has definite semantics regarding space complexity: if the base case uses O(1) space, each recursive step uses O(1) space beyond that used by the next lower level, and the recursion is k levels deep, then the space complexity is O(k). For Quicksort, k = log(n), so Quicksort uses O(log n) space. This is an inherent property of the algorithm and is entirely independent of language. $\endgroup$ – Ted Hopp Jan 1 '12 at 2:36
  • 2
    $\begingroup$ What about Chicken scheme for instance? No function in that implementation ever returns as everything is implemented as continuations that delve further into the "callstack". $\endgroup$ – Thomas Eding Jan 1 '12 at 2:50
  • 2
    $\begingroup$ @TedHopp: I think that what trinithis is saying is that something like whether “each recursive step uses O(1) space beyond that used by the next lower level” or not is determined only after giving the precise semantics of recursion such as whether tail call optimization is performed or not. I agree with trinithis that this level of semantics is often considered outside of a description of an algorithm, and therefore it is often meaningless to discuss whether the space complexity of a recursive algorithm is O(1) or not. (more) $\endgroup$ – Tsuyoshi Ito Jan 2 '12 at 23:08
  • 2
    $\begingroup$ @TedHopp: (cond’d) For example, “What is the space complexity of the factorial implemented by a recursion?” is not answerable because the description is not precise enough to talk about its space complexity. $\endgroup$ – Tsuyoshi Ito Jan 2 '12 at 23:08
  • 2
    $\begingroup$ @TsuyoshiIto, the jump from what this answer says and your interpretation of what it means seems like magic to me. I agree with two points made here. One by you: To talk about the space usage of recursive algorithms, you need to have a computational model that clarifies what is the space usage of function calls. One by trinithis: It really is about how function calls work, not necessarily recursive ones; to see this, thing about continuation-passing style programs. But statements like "talking about whether recursion has in-place semantics is nonsense" do not seem to address the question. $\endgroup$ – Radu GRIGore Jan 3 '12 at 22:36
8
+25
$\begingroup$

Although not for sorting, note that there are algorithms that may naturally be described using recursion but that do not require storage of a call stack. For instance, quickselect can be described as a modified version of quicksort that makes only one of the two recursive calls of quicksort; however, using tail recursion for this call avoids the need for a call stack.

Similarly, reverse search procedures (e.g. for listing the vertices of a convex polytope or for various other combinatorial enumeration procedures) are really just performing a recursive traversal of some implicitly-defined tree, but don't need to store more than a constant number of tree nodes at a time — in this case there is more than one recursive call from each call, but the call stack does not need to be stored because it can instead be calculated from the structure of the tree that is being traversed.

$\endgroup$
  • 1
    $\begingroup$ The second part reminds me of a cute puzzle I saw recently: Do an in-order traversal of a binary tree using $O(1)$ extra memory. $\endgroup$ – Radu GRIGore Jan 3 '12 at 22:26
  • $\begingroup$ It took me several days, but I wrote a quick-sort variation that uses O(1) stack memory, though my peers at StackOverflow immediately called into question if it is still a quick-sort. $\endgroup$ – Mooing Duck Feb 26 '14 at 0:13
2
$\begingroup$

Who says that Quicksort is an in-place sort? There is a compact version of Quicksort that uses an in-place partition algorithm, but the overall space usage is, as you say, O(log n).

$\endgroup$
  • 1
    $\begingroup$ Yeah, I'm talking about the inplace version of Quicksort, but again in this inplace version there is inherent usage of O(log(n)) memory in the form of stack? so how is this inplace now? Am I missing somethig?! I believe inplace means you can't use more than a fixed amount of memory in your algorithm! $\endgroup$ – Alan Turing Jan 1 '12 at 1:46
0
$\begingroup$

All sorting algorithms on random-access arrays require O(lg(n)) space. Consider the size of the array indices. It requires ceil(lg(n)/lg(2)) bits to represent an array index variable that can hold n distinct values. If your data is in a random-access array, you will need at least one such variable. Therefore, there is a minimum bound of O(lg(n)) on your space complexity, regardless of what algorithm you use.

Note that mergesort cannot avoid this either. You can either have mergesort run in-place, in which case all merge phases (of which there are O(lg(n))) run in parallel for O(lg(n)) space complexity, or you do a non-in-place sort with O(n) space complexity, or you overwrite your input array, in which case you need that index variable again.

Because this bound is rather fundamental (and typically not a problem), usually one does not bother mentioning it.

$\endgroup$
  • 2
    $\begingroup$ Index size is a different issue (and often assumed to be O(1) in algorithmics), if you are counting it then quicksort and mergesort require O(log^2 n) memory, while insertionsort is O(log n). And in this setting, it is important to mention that time complexity of many sorting algorithms stops being O(n log n), since array access is then O(log n) not O(1). $\endgroup$ – sdcvvc Jan 1 '12 at 3:12
  • $\begingroup$ @bdonlan What you are saying is certainly a good point, but isn't the issue with the size of index more of an architectural issue rather than algorithmic. I mean, in analyzing algorithms we just don't care about practical limit in variables? But in the question I am asking its bit different, here number of such variables used is dependent on size of input and is independent of architecture... $\endgroup$ – Alan Turing Jan 1 '12 at 7:57
  • 3
    $\begingroup$ Index size is usually not considered because we're usually talking about a finite machine where the index size is a constant: log(address_space_size). (We usually use an int to index into an int[10] and the same int to index into an int[500000].) Despite the fact that all problems are thus theoretically O(1) (since we have a finite space), we're interested in how much heap (or other auxiliary) storage will be needed as the problem grows. The size of index variables usually doesn't grow with problem size. $\endgroup$ – Ted Hopp Jan 2 '12 at 16:58
  • 2
    $\begingroup$ The standard integer RAM model assumes that each memory address holds a w-bit integer, for some integer w ≥ lg n. Standard operations on those integers—like comparisons, arithmetic, and indirection—require O(1) time. The standard definition of an in-place algorithm is one that uses O(1) additional words of memory. $\endgroup$ – Jeffε Jan 3 '12 at 14:01
  • 1
    $\begingroup$ @jpalecek: No, that's a stack of O(w) words, not a stack of O(1) words. The word size w is NOT considered constant. Operations on w-bit integers are assumed to take constant time because of low-level parallelism in the hardware. $\endgroup$ – Jeffε Jan 4 '12 at 21:04
0
$\begingroup$

how can it be called inplace sort?

Because O(log2 n) bits still isn't very much storage, and the theoretical contingent almost certainly appropriated the term "inplace" from the practitioners in the first place, anyway.

(Side node: quicksort's space usage can be made worst-case by performing tail-call optimization on the larger subproblem (thanks, Sedgewick).)

$\endgroup$
  • $\begingroup$ @Downvoter Why? $\endgroup$ – someone Jan 1 '12 at 2:15
  • 2
    $\begingroup$ -1 because "In place" by definition uses constant memory. Unrelated, how can you do TCO on qsort (without of course maintaining your own stack)? $\endgroup$ – Thomas Eding Jan 1 '12 at 2:17
  • $\begingroup$ @trinithis: He is refering to the well known trick of recursing first into the smaller sub-array after the partition step in order to avoid the worst case O(N) memory use from the naive implementation. And in-place does not mean constant memory. Do you know anyone that does not consider quicksort in-place (in comparison to things like mergesort)? $\endgroup$ – hugomg Jan 3 '12 at 18:37
  • 2
    $\begingroup$ @missingno: It sorts the array in-place. His answer on the other hand mentions memory usage that is not O(1) due to the recursive nature of the function call. In-place here is being used for two different things. $\endgroup$ – Thomas Eding Jan 4 '12 at 5:09
  • $\begingroup$ @missingno: In CompSci, "In Place" has a specific meaning, which is different from the colloquial. en.wikipedia.org/wiki/In-place_algorithm "An in-place algorithm is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space." $\endgroup$ – Mooing Duck Feb 26 '14 at 0:18
0
$\begingroup$

In-place sorting algorithms are called so because only a constant number of elements are out of the input (probably an array) at any given time during the sorting process. Recursion is only a technique that can be used to solve problems. It is defined as "calling itself directly or indirectly with an input of smaller size than the original problem size". They are completely two different ideas. So, there can be in place sorting algorithms which uses recursion.

$\endgroup$
0
$\begingroup$

Afaik, any programming language with good execution time optimizes tail recursion.

There are even algorithms for which it's easiest to code their "most in-place" variant in pure functional languages like Haskell because said algorithm requires considerable small modifications to a large data structure (see this question pertaining to an example).

I'll grant that functional languages aren't nearly as explicit with identfying their in-place data.

$\endgroup$
  • $\begingroup$ Hmm, but tail-recursion optimization isn't possible in all the cases! So, my question is actually for any generic recursive algorithm, its just that I gave some example :) $\endgroup$ – Alan Turing Jan 12 '12 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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