adplus-dvertising
frame-decoration

Question

The second smallest of n elements can be found with ............... comparisons in the worst case.

a.

n−1

b.

lg n

c.

n+ceil(lg n) - 2

d.

3n/2

Answer: (c).n+ceil(lg n) - 2

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. The second smallest of n elements can be found with ............... comparisons in the worst case.

Similar Questions

Discover Related MCQs

Q. Consider the following statements related to AND-OR Search algorithm.

S1: A solution is a subtree that has a goal node at every leaf.
S2: OR nodes are analogous to the branching in a deterministic environment.
S3: AND nodes are analogous to the branching in a non-deterministic environment.

Which of the following is true referencing the above statements?

Q. The solution of the recurrence relation
T(m) = T(3m/4) + 1 is:

Q. Consider the array A=<4, 1, 3, 2, 16, 9, 10, 14, 8, 7>. After building heap from the array A, the depth of the heap and the right child of max-heap are .............. and .................. respectively. (Root is at level 0).

Q. A hash function h defined h(key)=key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18?

Q. Which of the following algorithms solves the single-source shortest paths?

Q. A text is made up of the characters A, B, C, D, E each occurring with the probability 0.08, 0.40, 0.25, 0.15 and 0.12 respectively. The optimal coding technique will have the average length of:

Q. A binary search tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 19 leaves:

Q. Match the following with respect to algorithm paradigms :

List - I
(a) The 8-Queen’s problem
(b) Single-Source shortest paths
(c) STRASSEN’s Matrix multiplication
(d) Optimal binary search trees

List - II
(i) Dynamic programming
(ii) Divide and conquer
(iii) Greedy approach
(iv) Backtracking

Code:
(a) (b) (c) (d)

Q. The maximum number of comparisons needed to sort 9 items using radix sort is (assume each item is 5 digit octal number):

Q. A 5-ary tree is tree in which every internal node has exactly 5 children. The number of left nodes in such a tree with 8 internal nodes will be:

Q. Consider a Boolean function of ‘n’ variables. The order of an algorithm that determines whether the Boolean function produces a output 1 is:

Q. Consider an array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i< = n), the index of the parent is:

Q. The following numbers are inserted into an empty binary search tree in the given order:

10, 1, 3, 5, 15, 12, 16.

What is the height of the binary search tree?

Q. Let G be an undirected connected graph with distinct edge weight. Let Emax be the edge with maximum weight and Emin the edge with minimum weight. Which of the following statements is false?

Q. A list of n strings, each of length n, is sorted into lexicographic order using merge - sort algorithm. The worst case running time of this computation is:

Q. Postorder traversal of a given binary search tree T produces following sequence of keys:

3, 5, 7, 9, 4, 17, 16, 20, 18, 15, 14

Which one of the following sequences of keys can be the result of an in-order traversal of the tree T?

Q. The three aspects of Quantization, programmers generally concerned with are:

Q. The logic of pumping lemma is an example of ....................

Q. Heap allocation is required for languages that :

Q. Consider a full binary tree with n internal nodes, internal path length i, and external path length e. The internal path length of a full binary tree is the sum, taken over all nodes of the tree, of the depth of each node. Similarly, the external path length is the sum, taken over all leaves of the tree, of the depth of each leaf.
Which of the following is correct for the full binary tree?