Which of the following is best running time to n n2 − 1 sort integers in the range 0 to ?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. O(n)
Explanation
Write each number as two base-n digits and radix sort: two counting-sort passes, O(n).
More Data Structures and Algorithms questions
- Which of the following is application of depth- first search?
- Consider double hashing of the form h(k, i) = (h (k) + ih (k)) mod m 1 2 h (k) = k mod m where 1 h (k) = 1 + (k mod n) 2 n = m − 1 m = 701…
- Consider the complexity class as the ¯¯¯ L ∈ NP set of languages L such that , and the following two statements : S : P ⊆ CO − NP 1 S NP ≠…
- Consider the following steps : S 1 : Characterize the structure of an optimal solution S 2 : Compute the value of an optimal solution in bo…
- Consider the following properties with respect to G = (V , E) a flow network in which a flow is a f : V × V → R real-valued function : P :…
- Consider the graph shown below : Use Kruskal's algorithm to find the minimum spanning tree of the graph. The weight of this minimum spannin…