Question

The worst case complexity for insertion sort is _________

(a) O(n)

(b) O(log n)

(c) O(n^2)

(d) O(n log n)

The question was posed to me in a national level competition.

My question is taken from Algorithms topic in section Algorithms of Discrete Mathematics

Answer 1

Correct choice is (c) O(n^2)

Explanation: In worst case nth comparison are required to insert the nth element into correct position.