The worst case time complexity of insertion sort is O(n^2). What will be the worst case time complexity of insertion sort if the correct position for inserting element is calculated using binary search?

(a) O(nlogn)

(b) O(n^2)

(c) O(n)

(d) O(logn)

The question was asked by my school principal while I was bunking the class.

Question is taken from Insertion sort topic in portion Sorting of Data Structures & Algorithms II