GATE IT 2008 | Question: 43

Question

If we use Radix Sort to sort $n$ integers in the range $\left (n^{k/2}, n^k \right ]$, for some $k > 0$ which is independent of $n$, the time taken would be?

• A. $\Theta(n)$
• B. $\Theta(kn)$
• C. $\Theta(n \log n)$
• D. $\Theta(n^2)$

Comments

Hi @srestha, thanks for responding, the approach used by @Shivam Chauhan in the 2nd comment above which is not the answer, is as mentioned in clrs book. I can't seem to figure out if we are going wrong somewhere. Pls help. If you have the book pls refer to the last page of the radix sort explanation just before exercise.

---

I feel bad that I'm not able to solve such questions based on sorting-time-complexity. Please suggest sources from where should I study this?  :'(

---

Counting sort & Radix sort :-

1.  https://www.youtube.com/watch?v=E6zYX8Pf0W4
2. https://www.youtube.com/watch?v=PEgQtubYQvA&feature=emb_logo
3. https://www.youtube.com/watch?v=MNHdxQDUEyk&feature=emb_logo

Answer 1

Answer: C

The complexity of Radix Sort is $O(wn)$, for $n$ keys which are integers of word size $w$.

Here, $w = \log_2(n^k) = k \times \log_2(n)$

So, the complexity is $O(wn) = O(k \times \log_2(n) \times n)$, which leads to option C.

Comments

@Deepak Poonia Sir,

$Answer: option B$

Method 1: n elements range of elements n^(k/2) to n^k

No. of digits (d) = logbase10(n^k) = θ(klogn)
Radix sort time complexity : θ(n * k * logn)

$Method 2$ : n elements given

Convert each element into radix n number system. Time complexity for this n elements θ(n)

Number of digits is become log basen(n^k) = k digits.

Applying radix sort time complexity θ(n * k)

---

@sachin_mitt please reply to the comment of argharupa. I also have same doubt

---

Conversion from radix a to radix b is not a constant time operation.

Hence the 2nd approach  will not work(i.e will take more time)

Answer 2

TIME COMPLEXITY OF RADIX SORT IS THETA ((n+k)d))

where n= no of numbers

k= base of number system

d= no of digits.

Here let base is b. 

Numbers are are in range (n^k/2,n^k).

No of digits required= (log n^k)base b=k log n base b.

thus time complexity =( n+b) k log n base b.

Since b and k are constants with respect to n  time complexity = Θ(nlogn)

Comments

same doubt what to take base here?

---

Consider base as b. Base could be anything. You cant conclude base from the given information, so assume.

---

To make radix sort run in linear time we put b=O(n).. You can see the proof in cormen but isn't that necessary..

Useful link :

 https://www.youtube.com/watch?v=Nz1KZXbghj8 

Answer 3

I am not sure my approach is correct or not but I have seen something like this in CLRS.

When we represent n^k/2 and n^k in base n, we need atmost k+1 bits.

And to sort k+1 bit positions apply any stable sorting algorithm like counting sort(O(n) time ).

So, time complexity = O(k*n) i.e. apply counting sort for each of the k+1 bit positions.

So, answer (b).

If my approach is wrong,can anyone explain why ??

Comments

Source?

---

What I got :

TC Radix Sort::

O( d *( n+b) )

where, n= no. of inputs

b= n no.s represented in base b

d=no. of digits required to represent input no. in base b

Now, Mapping this to given ques..

n=n

b=(not mentioned)

d=log_bn^k as no.s in range n^k/2 to n^k

tc=O( log_bn^k * (n+b) )= O(nlogn) // Taking b and k as constants

Anything wrong above?

---

Think once that n^k has k+1 bits? It will have log_m(n^k) bits. Here they have mentioned integers. Therefore base m value will be 10. So no. of digits = log₁₀(n^k) = k* log₁₀(n)

Answer 4

Answer would be C.

P.S- The question mention "n integer values" somehow implies it is decimal representation system. So we can say k=10 and d=k*$log_{10}N$

Time complexity = O (n.log n)

Comments

@Nitesh Singh 2

why have u taken $k$ and $m$ differently?? both same. right??

---

I think both are different. m is the base of the number representation and k determines the range in which those n values lies.

Answer 5

Radix sort sorts numbers from LSB to MSB one column of digits at a time.

Each sort of a column (imagine a Matrix where each row is a candidate number) takes $O(n)$ time

Hence total time complexity would be $O(pn)$ where p = number of columns or the word length.

 

The maximum number we'd require to sort would be $n^k$. (given)
The word length of such a number would be $log (n^k)$ or $klogn$ or $O(logn)$ because k is independent of n.

Hence p = $O(logn)$

So, time complexity of radix sort here would be $O(pn) = O(nlogn)$

 

Option C

Answer 6

$Answer: option B$

Method 1: n elements range of elements n^(k/2) to n^k

No. of digits (d) = logbase10(n^k) = θ(klogn)
Radix sort time complexity : θ(n * k * logn)

$Method 2$ : n elements given

Convert each element into radix n number system. Time complexity for this n elements θ(n)

Number of digits is become log basen(n^k) = k digits.

Applying radix sort time complexity θ(n * k)