Bissoy.com
Doctors Medicines MCQs Q&A

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

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

The use of binary search reduces the time of finding the correct position from O(n) to O(logn). But the worst case of insertion sort remains O(n2) because of the series of swapping operations required for each insertion.

Related Questions

We create a binary search tree B1 by inserting the numbers 1, 2, 3, 4, 5 into an empty binary search tree. We create another binary search tree B2 by inserting the numbers into an empty binary search tree in the reverse order. What is the difference between the right-most element of B1 and the left-most element of B2?
The usual O(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
Consider the relation Emp-Dept with SSn as key Ename SSn EAddr Dept. No Dept. Name Dept. Manager SSn   Which of the following is (are) invalid operation(s)? a) Inserting an employee without name and address b) Inserting an employee with only SSn c) Inserting a department with no employee d) Inserting an employee without SSn
Binary tree sort implemented using a self balancing binary search tree takes O(n log n) time in the worst case but still it is slower than merge sort.
The binary tree sort implemented using a self – balancing binary search tree takes ______ time is worst case.
How many swaps will be required in the worst case to sort an array having n elements using binary insertion sort?
Consider the following statements: I. The smallest element in a max-heap is always at a leaf node II. The second largest element in a max-heap is always a child of the root node III. A max-heap can be constructed from a binary search tree in Θ(n) time IV. A binary search tree can be constructed from a max-heap in Θ(n) time Which of the above statements are TRUE?
What is the worst case time complexity of binary insertion sort?
Match List I with List II List I List II (A) Greedy Best-First Search (I) Space complexity is O(d) where d = depth of the deepest optimal solution (B) A* (II) Incomplete even if the search space is finite. (C) Recursive Best-First Search (III) Optimal if optimal solution is reachable: otherwise, returns the best reachable optimal solution. (D) SMA* (IV) Computation and space complexity is too high.   Choose the correct answer from the options given below:
What is the worst case time complexity of inserting an element into the sorted array?