Test: Divide & Conquer- 3 - Computer Science Engineering (CSE) MCQ

Priority queue can be implemented using an array, a linked list, a heap data structure. Among these data structures, heap data structure provides an efficient implementation of priority queues. In a normal queue, queue is implemented based on FIFO but in priority queue nodes are removed based on the priority.
Time complexity of priority queue using binary heap or binary search tree :

• Insert operation takes : O( log n )
• Delete operation takes : O (log n )

Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys which share same position and value. So it take O(n) time.

Binary search only half of the array.
So,  

Connected components of a graph can be computed in linear time by using either breadth- first search or depth-first search.

A merge sort is comparisbn based sorting algorithm and divide-and-conquer algorithm.

The number of comparisons required in the worst case is O(m + n).

Both of given cases are Quicksort Worst cases problem, so comparisons are equal.

Use Master Theorem 

A sorting algorithm is called stable if it keeps elements with equal keys in the same relative order in the output as they were in the input.
For example in the following input the two 4’s are indistinguishable. 1,4_a, 3, 4_b, 2 and so the output of a stable sorting algorithm must be:
1, 2, 3, 4_a, 4_b
Bubble sort, merge sort, counting sort, insertion sort are stable sorting algorithms.

Given: 20, 47, 15, 8, 9, 4, 40, 30, 12, 17
2-way merge sort so group of 2 is taken at once.
2nd pass:

The order of elements after second pass of the algorithm is 8, 15, 20, 47, 4, 9, 30, 40, 12, 17.