The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 votes

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

Following algorithm(s) can be used to sort $n$ in the range $[1.....n^3]$ in $O(n)$ time

  1. Heap sort
  2. Quick sort
  3. Merge sort
  4. Radix sort
asked in Algorithms by Veteran (69k points)
edited by | 927 views

Radix Sort uses Counting Sort as sub-routine, if there are d digits numbers in the input, then we need d passes of the Radix Sort, and each pass needs O(n+k) time, so total time comes to $O(d*(n+k))$.
As the input elements are in the range of $[1....n^3]$ we can convert each element into base n then each number needs $log_n(n^3) = 3$ digits.
So, there will only need to be 3 passes, for each pass, there are n possible values which can be taken on.

So, we can use counting sort in $O(n)$ time.

Radix Sort 

3 Answers

+14 votes
Best answer

Answer is (D) Part.

Although people have provided correct  answers but it seems some more explanation is required.
Let there be $\mathbf{d}$ digits in max input integer, b is the base for representing input numbers and $\mathbf{n}$ is total numbers then Radix Sort takes $\mathbf{O(d*(n+b))}$ time. Sorting is performed from least significant digit to most significant digit. 

For example, for decimal system, $b$ is $10$. What is the value of $d$? If $k$ is the maximum possible value, then $d$ would be $O(\log_b (k))$. So overall time complexity is $O((n+b) * \log_b(k))$. Which looks more than the time complexity of comparison based sorting algorithms for a large $k$. Let us first limit $k$. Let $k \leqslant n^{c}$ where $c$ is a constant. In that case, the complexity becomes $O(n \log_b(n))$. But it still does not beat comparison based sorting algorithms.
What if we make value of $b$ larger?. What should be the value of $b$ to make the time complexity linear? If we set $\mathbf{b}$ as $\mathbf{n}$ then  we will get the time complexity as $O(n)$.

In other words, we can sort an array of integers with range from $1$ to $n^{c}$, If the numbers are represented in base $n$ (or every digit takes $\log_2(n)$ bits).


Reference  -->

answered by Veteran (14.7k points)
edited by
Gd explanation ....
+11 votes
Answer :-> D

As no comparison based sort can ever do any better than nlogn (Unless in special cases) a,b,c are eliminated. nlogn is lower bound for comparison based sorting.

As Radix sort is not comparison based sort (it is counting sort) D is correct !
answered by Veteran (49.5k points)
shouldn't it include quick sort also?here it is asked to sort 1 element i.e. 'n' in the range 1 to $n^3$.
what would be the complexity of the radix sort in this case?
time complexity of radix sort is theta ((n+k)d)
counting sort will take theta(n^3)??
+9 votes
Answer: D

Radix sort complexity is O(wn) for n keys which are integers of word size w.
answered by Veteran (36.4k points)

Here word size = ( 1 to n3) . = 3 log10(n) ... 

So again time complexity would be = n log n .

Correct me if I am wrong ..

I think @Akash gave correct reason. Because no comparison based sorting in all cases(best, avg., worst) gives O(n) complexity
Nice explanation.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,170 questions
40,846 answers
39,703 users