What is the Space complexity of insertion sort algorithm?

Answer 1

Insertion sort is an in-place sorting algorithm, meaning that it requires little to no extra storage. In the case of insertion sort, only a single list element needs to be stored outside of the initial data, making the space complexity O(1).

Answer 2

Insertion sort splits a data sequence in two; a sorted portion at the beginning of the sequence followed by an unsorted sequence. Initially, the sorted sequence has just one element because a sequence of 1 can always be regarded as being sorted. We then take the first unsorted element and insert it in its proper place within the sorted sequence. This is achieved by removing it from the sequence (creating a gap in the sequence). We then look at the element to the left of the gap. If it is larger than the element we removed we move the element one position to the right, effectively moving the gap one position to the left. We repeat the process until the element to the left of the gap is smaller or equal to the removed element, or we reach the start of the sequence. We then insert the removed element into the gap, increasing the sorted set by 1 element and reducing the unsorted set by 1 element. We repeat the process until the unsorted set is empty.

The best case for insertion sort is O(n) time because we need to make at least one complete pass over the set. The best case occurs when the set is already sorted and therefore incurs no moves, but we still have to make a single pass over the set to confirm this. In reality, the complexity is O(n-1) because the first element is known to be sorted, however we can ignore minor differences like -1. Moreover, we have to move n-1 elements out of the set and back in again in the same place, but these two operations occur whether an element moves or not, so we can discount it.

The worst case occurs when the set is in reverse order. However, if we count the number of moves in the worst case we find there are k moves on the kth pass, where k<n. Thus for a set of 10 elements, there are 1+2+3+4+5+6+7+8+9 moves in the worst case, which is 45 (a triangular number). Unfortunately, there is no simple notation for triangular numbers, but time complexities are merely intended to give us an indication of performance. We can clearly see that to move n elements we need to make n passes, thus the worst case time-complexity can be denoted as O(n*n).

Answer 3

It depends on whether the structure is a linked list or a binary tree. Linked lists are generally O(n), with an expected average of O(n/2). With binary trees, the average is O(log n) if the tree is balanced.

Answer 4

O(n2)