Given an unsorted array. The array has this property that every elemen

Back to the 2022 paper

Module 1: Introduction and Complexity Analysis

20222m

Given an unsorted array. The array has this property that every element in array is at most $k$ distance from its position in sorted array where $k$ is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?

(i) Insertion sort with time complexity $O(kn)$
(ii) Heap sort with time complexity $O(n \log k)$
(iii) Quick sort with time complexity $O(k \log k)$
(iv) Merge sort with time complexity $O(k \log k)$

Search Google Ask AI

Similar questions

Design and Analysis of Algorithms Which sorting algorithm is considered stable and has a time complexity of O(n^2)? (i) Quick sort (ii) Merge sort (iii) Insertion sort (iv) Selection sort20232m Design and Analysis of Algorithms Which of the following sorting algorithms has the best time complexity in the average case? (i) Bubble sort (ii) Insertion sort (iii) Quick sort (iv) Selection sort20232m Design & Analysis of AlgorithmsWorst-case complexity of heap sort is - - (i) O(\log n) - (ii) O(n^2) - (iii) O(n \log n) - (iv) O(n)20242m Design & Analysis of AlgorithmsThe worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are: - (i) \Theta(n \log n), \Theta(n \log n) and \Theta(n^2) - (ii) \Theta(n^2), \Theta(n^2) and \Theta(n \log n) - (iii) \Theta(n^2), \Theta(n \log n) and \Theta(n \log n) - (iv) \Theta(n^2), \Theta(n \log n) and \Theta(n^2)20242m

PreviousIn linear search algorithm the worst case occurs when: - (i) the item is somewhere in the middle of the array - (ii) the item is not in the array at all - (iii) the item is the last element in the array - (iv) the item is the last element in the array or is not there at all NextApproach of dynamic programming is similar to: - (i) parsing - (ii) hash table - (iii) divide and conquer algorithm - (iv) greedy algorithm