The Gateway to Computer Science Excellence
0 votes

Observe that the while loop of the INSERTION-SORT procedure uses a linear search to scan (backward) through the sorted subarray $A[i\dots j-1]$ Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to $\Theta(n\ lg\ n)$?

in Algorithms by Boss (42.4k points) | 20 views

1 Answer

0 votes

Although by using Binary search instead of using linear search, the search time for finding the correct position for the element will decrease (becomes $\Theta(log\ n)$) but the swaps that we need to do to create the place for inserting that element will not change. So the overall time complexity will not be effected.

by Boss (23.8k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,274 answers
104,800 users