adplus-dvertising
frame-decoration

Question

If there are n integers to sort, each integer has d digits, and each digit is in the set  {1, 2, …, k}, radix sort can sort the numbers in:

a.

O (k (n + d))

b.

O (d (n + k))

c.

O ((n + k) l g d)

d.

O ((n + d) l g k)

Answer: (b).O (d (n + k))

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. If there are n integers to sort, each integer has d digits, and each digit is in the set  {1, 2, …, k}, radix sort can sort the numbers in:

Similar Questions

Discover Related MCQs

Q. Match the following:

a. Prim’s algorithm                  i. O(V^2E)
b. Bellman-Ford algorithm     ii. O(VE lgV)
c. Floyd-Warshall algorithm   iii. O(E lgV)
d. Johnson’s algorithm           iv. O(V^3)

Where V is the set of nodes and E is the set of edges in the graph.

Codes :
     a    b   c   d

Q. Constructors have ............. return type.

Q. Method over-riding can be prevented by using final as a modifier at ...............

Q. Which of the following is a correct statement?

Q. Which of the following is not a correct statement?

Q. Given the following statements:

(a) To implement Abstract Data Type, a programming language require a syntactic unit to encapsulate type definition.
(b) To implement ADT, a programming language requires some primitive operations that are built in the language processor.
(c) C++, Ada, Java 5.0, C#2005 provide support for parameterised ADT.

Which one of the following options is correct?

Q. Match the following types of variables with the corresponding programming languages:

(a) Static variables                   (i) Local variables in Pascal
(b) Stack dynamic                    (ii) All variables in APL
(c) Explicit heap dynamic       (iii) Fortran 77
(d) Implicit heap dynamic       (iv) All objects in JAVA

Codes:
      (a)   (b)   (c)   (d)

Q. The number of different binary trees with 6 nodes is .............

Q. Let A[1...n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i,j) is called an inversion of A. What is the expected number of inversions in any permutation on n elements?

Q. Which one of the following array represents a binary max-heap?

Q. Match the following:

(a) Huffman codes                              (i) O(n2)
(b) Optimal polygon triangulation     (ii) θ(n3)
(c) Activity selection problem             (iii) O(nlgn)
(d) Quicksort                                         (iv) θ(n)

Codes:
      (a)   (b)   (c)   (d)

Q. Suppose that we have numbers between 1 and 1000 in a binary search tree and want to search for the number 364. Which of the following sequences could not be the sequence of nodes examined?

Q. A triangulation of a polygon is a set of T chords that divide the polygon into disjoint triangles. Every triangulation of n-vertex convex polygon has ................ chords and divides the polygon into ............... triangles.

Q. Implicit return type of a class constructor is:

Q. It is possible to define a class within a class termed as nested class. There are ............ types of nested classes.

Q. Which of the following statements is correct?

Q. Which of the following statements is correct?

Q. When one object reference variable is assigned to another object reference variable then

Q. Which of the following statement(s) is/are false?

(a) A connected multigraph has an Euler Circuit if and only if each of its vertices has even degree.
(b) A connected multigraph has an Euler Path but not an Euler Circuit if and only if it has exactly two vertices of odd degree.
(c) A complete graph (Kn) has a Hamilton Circuit whenever n≥3
(d) A cycle over six vertices (C6) is not a bipartite graph but a complete graph over 3 vertices is bipartite.

Q. Consider the following two statements:

(a) A publicly derived class is a subtype of its base class.
(b) Inheritance provides for code reuse.

Which of the above statements is correct?