Question

Any algorithm that sorts by exchanging adjacent elements require O(N^2) on average.

(a) True

(b) False

This question was posed to me during an interview.

My doubt stems from Insertion sort topic in portion Sorting of Data Structures & Algorithms II

Answer 1

Correct answer is (a) True

To explain: Each swap removes only one inversion, so O(N^2) swaps are required.