Select all the statements below which are TRUE. Select all the statements below

ID: 3722685 • Letter: S

Question

Select all the statements below which are TRUE.

Select all the statements below which are TRUE. If f(n) = o(g(n)), then g(n)-(f(n)). Dictionary operations (insert, delete, search) are implemented in constant time using direct- address tables. Consider a decision tree T corresponding to a comparison sort of n = 4 elements. Then the number of leaves can be 20. O Any comparison sort algorithm has the worst case running time (nIgn). Let A[1.n] be a min-heap. Then the third order statistics is always A[3 Merge sort algorithm has the sorting in place property.

Explanation / Answer

1) if f(n) = o(g(n)) then f(n) = w (f(N))

if f(n) = o(g(n)) then f(n) <= g(n)

g(n) > f(n) so g(n) = w (f(n))

Ans true

2) True

Dictionary operation takes O(1) in general

3) True

4) Any Comparasion sort has algorith has the worst case running time (nlogn)

Ans : True

3) Let A[1..n] be a min-heap . Then tird order statistice is always A[3]

In min-heap kth order statistic can be found in A [2..2k -1] for k>1

A[3] can be found in [2,3,4,5,6,7]

Ans : False

6) Merge sort algorith has the sroting in place property

The standard merge sort on an array is not an in-place algorithm, since it requires O(N) additional space to perform the merge.
Ans : False