0 votes 0 votes rajoramanoj asked Nov 6, 2017 rajoramanoj 622 views answer comment Share Follow See all 14 Comments See all 14 14 Comments reply Show 11 previous comments chandra sai commented Nov 6, 2017 reply Follow Share @rajoramanoj in insertion sort we consider first element as sorted and then insert 2nd element by comparing with first element .so now those two elements form sorted array. so if we perform binary search instead of linear search to find the position to insert next element to this already sorted array, we get an overall O(nlogn) comparisons . isn't it ? correct me if i am wrong! 0 votes 0 votes rajoramanoj commented Nov 6, 2017 reply Follow Share you are not correct now also bcoz if we use BS instead of LS first we consider for 1 element : find place = logn comparisions right shift = n swaps total = n+logn now we consider for n elements : =n(n+logn) =n2+nlogn =O(n2) 0 votes 0 votes chandra sai commented Nov 6, 2017 reply Follow Share @rajoramanoj in the question it is specified that complexity is measured in terms of number of comparisons only.(not number of shifts) so i think O(nlogn) 0 votes 0 votes Please log in or register to add a comment.