Insertion sort time complexity

#1

how is the time complexity of insertion sort O(n2)

#2

hi @priyamthakuria27 please refer to this link https://www.geeksforgeeks.org/time-complexity-insertion-sort-inversions/

#3

okay.
please explain this question once.
Q8. Insertion Sort 2

The ususal O(n^2) implementation of insertion sort uses the linear search to to identify the position where an element is to be inserted into the already sorted part of the array. If instead, we use binary search to identify the position the worst case running time will be:

O(n)

O(nlogn)

O(n^2)

O(n(logn)^2)

#4

@priyamthakuria27 O(n) time is spent in finding the correct place for insertion. If that is done via binary search then the total time taken will be O(logn). So instead now the time complexity will come down from O(n*n) to O(nlogn)