Data Structures and Algorithms The Complete Masterclass - Insertion Sort Complexity

The video tutorial explains the Big O complexity of insertion sort, focusing on both worst-case and best-case scenarios. The worst-case scenario involves an N square complexity due to the need for multiple comparisons, while the best-case scenario is linear, O of N, as the list is already sorted. The tutorial concludes with a brief summary and a preview of the next lecture.

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

• O(N log N)

• O(log N)

• O(N^2)

• O(N)

In the worst-case scenario, how many comparisons are made for each element in insertion sort?

• log N comparisons

• N comparisons

• N-1 comparisons

• N^2 comparisons

Which of the following lists represents the worst-case scenario for insertion sort?

• [3, 1, 4, 5, 2]

• [2, 3, 1, 5, 4]

• [5, 4, 3, 2, 1]

• [1, 2, 3, 4, 5]

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

• O(N)

• O(N^2)

• O(log N)

• O(N log N)

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

• The list is empty.

• The list contains duplicate elements.

• The list is reverse sorted.

• The list is already sorted.