Question 3971 – 2006 December UGC NET Paper 1
January 20, 2024Question 9600 – GATE 2003
January 20, 2024Question 9600 – GATE 2003
The usual Θ(n2) implementation of Insertion Sort to sort an array uses linear search 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
Correct Answer: A
Question 22 Explanation:
While using Insertion sort to sort array by using linear search then time complexity = Θ(n2)
Instead, linear search use binary search then (log n) will be the worst case time complexity of binary search and performing n swaps to place an element in right position for the corresponding n elements
i.e., n×(logn+n)
Θ((n×logn)+n2)
Θ(n2)
Remains same.
Instead, linear search use binary search then (log n) will be the worst case time complexity of binary search and performing n swaps to place an element in right position for the corresponding n elements
i.e., n×(logn+n)
Θ((n×logn)+n2)
Θ(n2)
Remains same.
remain Θ(n2)
become Θ(n (log n)2)
become Θ(n log n)
become Θ(n)