Question

Insertion sort will have a time complexity of ______ in the worst case.

• A. n$^3$
• B. log(n)
• C. n
• D. n$^2$

Hint:

Remember these Insertion Sort complexities:
- Best Case (already sorted array) = $O(n)$ comparisons.
- Worst Case (reverse sorted array) = $O(n^2)$ comparisons.
- Average Case = $O(n^2)$ comparisons.

Answer 1

The Correct Option is D

Step 1: Understanding the Question:
The question asks for the worst-case asymptotic time complexity (Big-O) of the Insertion Sort algorithm.

Step 2: Key Operational Logic of Insertion Sort:
- Insertion sort works by taking elements one by one from an unsorted portion of an array and inserting them into their correct relative positions in a sorted portion.
- The worst-case scenario occurs when the input array is sorted in exact reverse order.

Step 3: Detailed Explanation:
- Let us calculate the number of comparisons made in the worst-case scenario for an array of size $n$:
- To insert the 2nd element, we compare it with the 1st element (1 comparison).
- To insert the 3rd element, we may compare it with the 2nd and 1st elements (2 comparisons).
- To insert the $i$-th element, we must compare it with all $i-1$ elements in the sorted portion ($i-1$ comparisons).
- Summing up all comparisons for an array of size $n$:
\[ \text{Total Comparisons} = 1 + 2 + 3 + \dots + (n-1) \]
- Using the standard summation formula for the first $n-1$ integers:
\[ \text{Total Comparisons} = \frac{(n-1) \times n}{2} = \frac{n^2 - n}{2} \]
- In Big-O notation, we drop the lower-order term ($n$) and the constant fraction ($1/2$), leaving:
\[ T(n) = O(n^2) \]
- Thus, the worst-case time complexity of insertion sort is $O(n^2)$.

Step 4: Final Answer:
The worst-case time complexity of Insertion Sort is $O(n^2)$.
Hence, option (D) is the correct choice.