Insertion Sort Complexity

The video tutorial explains the Big O complexity of insertion sort, focusing on both worst and best case scenarios. The worst case is O(n^2), where each element is compared with all previous elements. The best case is O(n), where the list is already sorted, and no comparisons are needed. The tutorial concludes with a brief summary and a preview of the next lecture.

What is the time complexity of insertion sort in the worst-case scenario?

• O(n)

• O(n^2)

• O(n log n)

• O(log n)

In the worst-case scenario of insertion sort, what kind of list arrangement leads to O(n^2) complexity?

• A sorted list

• A reverse-sorted list

• A list with random elements

• A list with all identical elements

During the insertion sort process, what happens to an element when it is compared with the sorted portion of the list?

• It is removed from the list

• It is inserted at the correct position in the sorted portion

• It is always moved to the end of the list

• It is swapped with the first element

What is the time complexity of insertion sort in the best-case scenario?

• O(n log n)

• O(n^2)

• O(n)

• O(log n)

In the best-case scenario for insertion sort, why is the inner loop not utilized?

• Because the list is empty

• Because the list is already sorted

• Because the list is reverse-sorted

• Because the list contains only one element