The Gateway to Computer Science Excellence

+42 votes

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?

- $\Theta(n)$
- $\Theta(kn)$
- $\Theta(n \log n)$
- $\Theta(n^2)$

+6

Given **n b-bit **numbers and positive integer **r$\leq$b , radix sort sorts in Θ($(\frac{b}{r})(n+2^{r})$) time .**

Now 2^{b} > = n^{k} so b $\geq$ $\lg n^{k}$

**To minimize expression $(\frac{b}{r})(n+2^{r})$ **we take r = $\lg n$ and time comes up **Θ($\frac{bn}{\lg n}$)**

Substituing value of b = $\lg n^{k}$

We get answer as **Θ(kn****)**

@Arjun sir @Bikram sir @Habibkhan sir @sourav. sir @srestha mam Please explain where am I wrong?

+1

As I know radix sort complexity is given by

Thetha(d(k+n))

where n is numbers , d is digits of n and k is range .

Can any one describe it on this form ?

Thetha(d(k+n))

where n is numbers , d is digits of n and k is range .

Can any one describe it on this form ?

0

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.

+43 votes

Best answer

+1

for some K > 0 which is independent of n alredy given in quetion then why ur asking with respect to n.

+7

Yes, $k$ is constant with respect to $n$. The question says time for sorting $n$ numbers. The input size is $n$, and since $k$ is constant with respect to $n$, we have $O(kn\log n) = O(n \log n)$

0

Concept is right but base should be 10 as its decimal number .albeit it doesnt have any sence for this question.

+12

@Ruple: Nopes. Base can be any positive integer for radix sort's complexity to work. For example, if you're sorting bitstrings using radix sort, your base would be $2$. If you have octal numbers in your list, you can radix sort them using the base $8$ for $\log$

However, the point here is of the asymptotic complexity of the answer, which is independent of the base of the $\log$ here.

0

We have to sort n integers so here representation is decimal ..for that particular question i said base would me 10 ..didnt generalize it..

+3

umm.. how exactly did you conclude that it was decimal representation (base $10$) !? All that is said is that you have $n$ integers. Can you not have a finite list of $n$ integers in binary(base $2$) or octal(base $8$).

How does having a list of numbers tell you anything about their representation? They could be in base $\pi$ for all you know!

How does having a list of numbers tell you anything about their representation? They could be in base $\pi$ for all you know!

0

Here the number of elements to be sorted is not n but it is of the order of n^k. The number of digits is log(n^k)=k log(n) . So the time taken should be n^k log(n). Please correct me if I am wrong.

+38 votes

**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)**

+3 votes

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 ??

+3

We can convert the number to base n in O(n) time.

Overall complexity would be O(n)+O(nk)=O(nk) only.

Overall complexity would be O(n)+O(nk)=O(nk) only.

+1

Hi @VS, I think you are correct.

Other viewers please refer --> http://www.geeksforgeeks.org/radix-sort/

**Check section "**What is the running time of Radix Sort?"

I hope this helps.

+1

But a proper answer would be O(n$\log_m{n}$).

@Xylene Sir, She is also correct. I have already mentioned whatever is mentioned just now via reference link.

O($\log_m{n}$*(Total numbers+ Base of numbers)).

Think twice before down voting.

Sure Sir. But same thing is mentioned in the link shared by me but somebody down voted it. :(

+1

@Chhotu

Radix Sort takes O(d*(n+b)) time where b is the base for representing numbers

Why (+b) ? I could not imagine it logically :(

+3

@VS ji,

Because **n** may be less then **b. **

For example we have only 3 numbers but base is 10. In this case although n(=3) is less but we will check all b(=10 ) buckets(0-9).

+1

@VS ji,

Please refer -->

Here we have 10 buckets.

Source -->http://homes.soic.indiana.edu/classes/spring2016/csci/c343-yye/sort.php

+3

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_{b}n^{k} as no.s in range n^{k/2} to n^{k}

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

Anything wrong above?

+3 votes

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)

0 votes

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**

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,362 answers

198,491 comments

105,260 users