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?!

Improve this question
$\endgroup$
10
  • 32
    $\begingroup$ @AlanTuring: Could you please consider choosing a less questionable user name? $\endgroup$
    – Jukka Suomela
    Commented Jan 3, 2012 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
    Commented Jan 3, 2012 at 23:03
  • 4
    $\begingroup$ @Jukka Suomela, Why Alan Turing is questionable?! I admire him like many here! $\endgroup$
    – Alan Turing
    Commented Jan 4, 2012 at 1:37
  • 9
    $\begingroup$ I think by "questionable", @JukkaSuomela means "presumptuous". $\endgroup$
    – Jeffε
    Commented Jan 4, 2012 at 21:01
  • 8
    $\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
    Commented Jan 5, 2012 at 0:58

7 Answers 7

Reset to default
13
$\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.

Improve this answer
$\endgroup$
10
  • 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
    Commented Jan 1, 2012 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
    Commented Jan 1, 2012 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
    Commented Jan 2, 2012 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
    Commented Jan 2, 2012 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
    Commented Jan 3, 2012 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.

Improve this answer
$\endgroup$
2
  • 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
    Commented Jan 3, 2012 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
    Commented Feb 26, 2014 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).

Improve this answer
$\endgroup$
1
  • 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
    Commented Jan 1, 2012 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.

Improve this answer
$\endgroup$
7
  • 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
    Commented Jan 1, 2012 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
    Commented Jan 1, 2012 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
    Commented Jan 2, 2012 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ε
    Commented Jan 3, 2012 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ε
    Commented Jan 4, 2012 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).)

Improve this answer
$\endgroup$
5
  • $\begingroup$ @Downvoter Why? $\endgroup$
    – someone
    Commented Jan 1, 2012 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
    Commented Jan 1, 2012 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
    Commented Jan 3, 2012 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
    Commented Jan 4, 2012 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
    Commented Feb 26, 2014 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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Jan 12, 2012 at 20:49

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.