Scribd
Upload
2 views1 page

Insertion Sort Algorithm and Complexity

The Insertion Sort algorithm sorts an array by repeatedly taking an element and inserting it into its correct position within the sorted portion of the array. Its time complexity is O(n) in the best case (already sorted), O(n²) in average and worst cases (reverse sorted), while its space complexity is O(1). The algorithm is stable and operates in-place.

Uploaded by

Aparna Das
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views1 page

Insertion Sort Algorithm and Complexity

The Insertion Sort algorithm sorts an array by repeatedly taking an element and inserting it into its correct position within the sorted portion of the array. Its time complexity is O(n) in the best case (already sorted), O(n²) in average and worst cases (reverse sorted), while its space complexity is O(1). The algorithm is stable and operates in-place.

Uploaded by

Aparna Das
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Insertion Sort Algorithm

InsertionSort(A, n)
for i = 1 to n-1
key = A[i]
j=i-1
while (j >= 0 and A[j] > key)
A[j+1] = A[j]
j=j-1
A[j+1] = key

Time Complexity Analysis


Best Case (Already Sorted):
Outer loop executes n-1 times, while loop performs only one comparison each iteration.
T(n) = c1(n-1) + c2(n-1) = O(n).

Average Case:
On average, each key is compared with about half of the sorted elements.
Comparisons ≈ n(n-1)/4 ⇒ O(n²).

Worst Case (Reverse Sorted):


For i-th iteration, the while loop executes i times.
Total operations = 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n²).

Space Complexity
Only one extra variable (key) and loop variables are used.
Extra Space = O(1).

Summary
Best Time: O(n)
Average Time: O(n²)
Worst Time: O(n²)
Space: O(1)
Stable: Yes
In-place: Yes

You might also like