What is the average case running time of an insertion sort algorithm?
(a) O(N)
(b) O(N log N)
(c) O(log N)
(d) O(N^2)
I had been asked this question at a job interview.
This intriguing question comes from Insertion sort in chapter Sorting of Data Structures & Algorithms II