Skip to main content

In-place and Out-of-place Algorithms

Algorithms in Computer Science are classified into various categories depending on diverse characteristics of the algorithms and also on the resource usage of them.

In-place and out-of-place are one of such categorization depending on the extra memory space used by an algorithm to solve a problem.

Let us consider each one separately.

In-place algorithms

  • In-place algorithms convert the input in to an output without allocating extra memory space for the process of problem solving. It uses the available space given as the input and replaces input with output.
  • An in-place algorithm can use some small amount of non-constant additional memory.
  • The additional space of O (log n) is the accepted limit but sometimes lower than O(n) is also approved.
  • Bubble sort and Selection sort are two in-place algorithms in the context.

Out-of-place algorithms

  • An out-of-place algorithm is the opposite of in-place and needs growing amount of memory (usually O(n) or bigger than that) to process the input into output.
  • The standard merge sort algorithm is an example of out-of-place algorithm as it requires O(n) extra space for merging.

When studying algorithms in Computer Science, we come across algorithms that fall into these two categories. Choosing what algorithm among them to be the best is subjective, yet it is good to know the following before you make that decision.

Working in-place is a good way to save time and space. An in-place algorithm avoids the cost of initializing or copying data structures.

But, an in-place algorithm can cause side effects. The input is usually destroyed to replace with output which can affect code outside of the method.

Therefore, generally out-of-place algorithms are considered safer because they avoid such side effects.

One should only use an in-place algorithm if the space is constrained or the original input is not useful anymore (even for debugging).

Thanks for reading! Let me know if this was helpful. See you with another post :)

Comments

Popular posts from this blog

Binary Search Implementation in JavaScript.

Searching algorithms are one of the main categories of algorithms in Computer Science which are studied by novice programmers and students as a preparation for their journeys ahead to become skilled programmers. This post contains a short yet, a composite description on Binary Search algorithm and an implementation written using JavaScript language. Let’s just start! Happy learning :). Binary Search is one of the most popular searching algorithms. It is easy to grasp the knowledge on this algorithm intuitively. It is a divide-and-conquer algorithm, that divides the input array roughly in half every time it checks whether an element of the array is the one, we’re looking for. Binary search has a complexity of O(log n) in the worst case and O(1) in the best case. Note: The input for a binary search algorithm should be a sorted list. Below is an iterative approach to implement a binary search in JavaScript. function binarySearch (sortedArray, key) { let high = sortedArray.length-1 le...
Why can't I pour my heart out? Why can't I heal myself? I deserve love, I deserve peace, I need to heal, I need to heal my body. I am greatly regretful for making myself suffer, my body is weakened and unhealthy, my body has been suffering for the things I have been going through mentally. I will love myself back, and heal my body, my mind and myself to become a beautiful being. That is the beginning of self love :* I will love myself again, like no one else ever did. Years of pent up pain, stress and hurt is weakening and making my body unhealthy.  I need to release all these to heal myself. I will fight through this, like no one ever did, I will love me and heal me,  What others has to give me is a not a parameter anymore.  I will give myself the best time and care.