Please state which is True and which is False Select all the statements below wh
ID: 3851675 • Letter: P
Question
Please state which is True and which is False
Select all the statements below which are TRUE. Inserting a value into a queue Q[1..n] takes (n) in the worst-case. Counting sort is stable. Let L be a singly-linked list with n elements, sorted in increasing order. Then inserting an element x takes (n) in the worst-case. For any min-heap A[1..n], the second order statistics is always A[2]. RANDOMIZED-SELECT is using divide-and-conquer. In each step, the algorithm is recursing on two subproblems of size n/2. If f(n) = (g(n)), then f(n) = O(g(n)).Explanation / Answer
[1] Queue Operate on First In First Out (FIFO)
The time complexity for insertion is O(1) for a single operation
ANSWER : FALSE
[2] Counting sort is a stable sort i.e., multiple keys with the same value are placed in the sorted array in the same order that they appear in the input array.
ANSWER : TRUE
[3] (1)
ANSWER : FALSE
[4] TRUE
[5] This algorithm is a modification of quicksort and takes time O(n), on average, on an input array of size n.
ANSWER : FALSE
[6] FALSE