Clever Geek Handbook

How does the sorting algorithm have a spatial complexity of O (1)?

I've been studying various sorting algorithms and their time and space complexities and have seen algorithms like bubble sort and bubble sort have O (1) spatial complexity.

This struck me as odd, because perhaps the lowest possible space complexity would be O (n) (as in memory needed to store a dataset and nothing else)?

+3


source to share


2 answers


Space complexity is the extra space complexity used by your algorithm, i.e. additional space you need besides the initial space occupied by the data. Bubble sort and insert sort only use constant extra space besides the original data, so they are O (1) in space complexity.



+6


source


The sorting algorithm has a spatial complexity of O (1) by allocating a constant amount of space, such as multiple variables to iterate over, etc., that are not proportional to the size of the input.

An example of a sorting algorithm that is not O (1) in terms of space would be most mergesort implementations that allocate an auxiliary array, making it O (n). Quicksort might look like O (1) in theory, but the call stack is considered to be space and is therefore called O (log n).



Examples of sorting algorithms with O (1) spatial complexity include: selection sort, insertion sort, shell sort, and heapsort.

+2


source






More articles:


All Articles