Question

__________ comparisons required to sort the list 1, 2, 3…….n using insertion sort.

(a) (n^2 + n + 2) / 2

(b) (n^3 + n – 2) / 2

(c) (n^2 + n – 2) / 2

(d) (n^2 – n – 2) / 2

This question was posed to me in an internship interview.

The doubt is from Algorithms topic in portion Algorithms of Discrete Mathematics

Answer 1

Right option is (c) (n^2 + n – 2) / 2

To explain I would say: 2+3+4+….6n = (n^2 + n – 2) / 2.