Question:
Consider following statements about time complexity :
A. Merge sort and heap sort have $O(n \log n)$ in worst case
B. Quick sort has $O(n \log n)$ in average case and $O(n^2)$ in worst case
C. Insertion sort is faster than merge sort for large $n$
D. Bubble sort is stable
E. Selection sort has fewer swap than insertion sort
Choose the correct answer from the options given below :
Consider following statements about time complexity :
A. Merge sort and heap sort have $O(n \log n)$ in worst case
B. Quick sort has $O(n \log n)$ in average case and $O(n^2)$ in worst case
C. Insertion sort is faster than merge sort for large $n$
D. Bubble sort is stable
E. Selection sort has fewer swap than insertion sort
Choose the correct answer from the options given below :
A. Merge sort and heap sort have $O(n \log n)$ in worst case
B. Quick sort has $O(n \log n)$ in average case and $O(n^2)$ in worst case
C. Insertion sort is faster than merge sort for large $n$
D. Bubble sort is stable
E. Selection sort has fewer swap than insertion sort
Choose the correct answer from the options given below :
Show Hint
Selection sort is the best choice when the cost of "swapping" memory is very high, because it minimizes the total number of swaps.
Updated On: Aug 6, 2026
- B, C, E only
- A, C, D only
- A, B, C only
- A, B, D, E only
Show Solution
Verified By Collegedunia
The Correct Option is D
Solution and Explanation
Concept:
• Algorithm analysis involves evaluating the performance (Time and Space complexity) of different sorting methods under various conditions (Worst, Average, and Best case).
Step 1: Evaluate log-linear sorts (A and B)
Merge sort and Heap sort both use a divide-and-conquer strategy (logarithmic levels) and process every element (linear work), leading to a guaranteed \(O(n \log n)\) complexity in all cases. Quick sort is also \(O(n \log n)\) on average but degrades to \(O(n^2)\) if the pivot choices are poor (e.g., sorted arrays). Statements A and B are Correct.
Step 2: Evaluate relative performance (C)
For large \(n\), an \(O(n \log n)\) algorithm (Merge sort) will always eventually be faster than an \(O(n^2)\) algorithm (Insertion sort). Insertion sort is only faster for very small arrays. Statement C is Incorrect.
Step 3: Evaluate Stability (D)
A sorting algorithm is stable if it preserves the relative order of elements with equal keys. Bubble sort only swaps adjacent elements if they are strictly out of order, making it stable. Statement D is Correct.
Step 4: Evaluate Swap efficiency (E)
Selection sort finds the minimum in each pass and performs exactly one swap. Insertion sort may perform up to \(O(n)\) swaps (or rather, shifts) for a single element to reach its destination. In terms of memory writes/swaps, Selection sort is superior. Statement E is Correct.
• Algorithm analysis involves evaluating the performance (Time and Space complexity) of different sorting methods under various conditions (Worst, Average, and Best case).
Step 1: Evaluate log-linear sorts (A and B)
Merge sort and Heap sort both use a divide-and-conquer strategy (logarithmic levels) and process every element (linear work), leading to a guaranteed \(O(n \log n)\) complexity in all cases. Quick sort is also \(O(n \log n)\) on average but degrades to \(O(n^2)\) if the pivot choices are poor (e.g., sorted arrays). Statements A and B are Correct.
Step 2: Evaluate relative performance (C)
For large \(n\), an \(O(n \log n)\) algorithm (Merge sort) will always eventually be faster than an \(O(n^2)\) algorithm (Insertion sort). Insertion sort is only faster for very small arrays. Statement C is Incorrect.
Step 3: Evaluate Stability (D)
A sorting algorithm is stable if it preserves the relative order of elements with equal keys. Bubble sort only swaps adjacent elements if they are strictly out of order, making it stable. Statement D is Correct.
Step 4: Evaluate Swap efficiency (E)
Selection sort finds the minimum in each pass and performs exactly one swap. Insertion sort may perform up to \(O(n)\) swaps (or rather, shifts) for a single element to reach its destination. In terms of memory writes/swaps, Selection sort is superior. Statement E is Correct.
Was this answer helpful?
0
0
Top CUET PG Data Science A.I Cyber Security and Computer Sci. Questions
- Choose the correct answer from the options given below:
(A). RAID 3 requires only a single redundant disk.
(B) In RAID 4 scheme, two different parity calculations are carried out and stored in separate blocks on different disks.
(C) RAID 5 distributes the parity strips across all disks.
(D) In RAID 2, the number of redundant disks are proportional to the log of the number of data disks. - In case of DMA, after the completion of the transfer, the processor is required to be notified of the completion. This is done through.
- In a two-level memory hierarchy, the access time of the cache memory is 12 nsec and the access time of the main memory is 1.5 msec. The hit ratio is 0.98. What is the average access time of the two-level memory system?
- Match List I with List II.
List I List II A. Supervisor mode I. Entered when the processor encounters a software interrupt instruction B. Abort Mode II. Entered in response to memory fault C. Fast Interrupt Mode III. Entered whenever the processor receives an interrupt signal from a designated fast interrupt source D. Interrupt Mode IV. Entered whenever the processor receives an interrupt signal from any other source - Deallocation of stack of thread and register contexts will take place.
View More Questions
Top CUET PG Algorithm Questions
- Match List I with List II.Choose the correct answer from the options given below:
LIST I LIST II (A) A* Algorithm (I) Space complexity is O4, where d = depth of the deepest optimal solution. (B) Recursive Best First Search (II) Incomplete even if the search space is finite. (C) Recursive Best First Search (III) Optimal, if the optimal solution is reachable, otherwise returns the best reachable optimal solution. (D) SMA* Algorithm (IV) Computation and space complexity is too high. - Match List I with List II
LIST I LIST II (A) limx→1(1 − x)1/x (I) e (B) limx→0 1/x ln(1 − x) (II) 1 (C) limx→0 (1 + x2)1/x (III) 0 (D) limx→∞ (1 + 1/x)x (IV) 2 - Equation x2 − 1 = 0 is required to be solved using Newton Raphson’s method with an initial guess x0 = −1. Then after one step of Newton’s method, the estimate x1 of the solution will be given by
- Match List I with List IIChoose the correct answer from the options given below:
LIST I LIST II (A) Floyd-Warshall algorithm for all pair shortest paths (I) Divide and Conquer (B) Prim’s algorithm (II) Greedy Paradigm (C) Hamiltonian Circuit (III) Backtracking (D) Merge Sort (IV) Dynamic Programming paradigm - A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst-case running time of this computation is:
View More Questions
Top CUET PG Questions
- Given below are two statements:
Statement I: For Plato the meaning of the word 'Justice' is basically a conception in the mind only.
Statement II: For Plato the meaning of the word 'Justice' is fixed, mind-independently
In the light of the above statements, choose the correct answer from the options given below: - What is the electron count of OS6CO182-?
- XeF4 hydrolysis gives A + B, HF, and Oxygen. Find A and B
- What is more basic in pyrol and pyridine?
- Hydrolysis of Al2C3, Be2?
View More Questions