What is the average case running time of an insertion sort algorithm?
(b) O(N log N)
(c) O(log N)
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