The Gateway to Computer Science Excellence
+42 votes
4.1k views

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?

  1. $\Theta(n)$
  2. $\Theta(kn)$
  3. $\Theta(n \log n)$
  4. $\Theta(n^2)$
in Algorithms by Boss (16.3k points)
edited by | 4.1k views
+2
I this question answer depends on Base. (B) and (C). Both are possible.
+6

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

Now 2b > = nk  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 ?
0

Time complexity of radix sort is O(kn) and space complexity O(K+n).

@hem chandra joshi

0

@Shivam Chauhan did your doubt get clarified? if yes please help. I am facing the same doubt.

0

@Aayush Tripathi

Why r we need to do $\frac{b}{r}?$

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.

5 Answers

+43 votes
Best answer

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.

by Boss (33.9k points)
edited by
0
Here it is not mentioned that k is constant
+8
@Amsar: $k$ is independent of $n$ means that $k$ is constant with respect to $n$.
0
But with respect to n.
+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
Thnks :)
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!
0
Yeah! You'r right.

Thank You.
0
What does the line k independent of n mean here?
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.
0

the key of the question that i understood as of now that K is independent of n means K is a constant hence time complexity would be O(n logn) but if K is dependent on n that it should be O(nk * log(base b)(n)).

0
$Is\ this\ the\ correct\ way\ to\ relate:$

$Radix\ sort: O(d(n+b))\  time\ \underline{where\ b: base}$

$\#\ of\ digits=d= log_{b}n^k=klog_{b}n$

$\therefore O\left(klog_{b}n(n+b)\right)=nlog_{b}n$
+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)

by Boss (17.7k points)
+3

@sushmita

Since b and k are constants with respect to n  time complexity

I am having one doubt.. it is said that k is constant wrt n but nothing is told about b isn't it? Then why can't we take base as n?

0

what does sort n integers mean? Now can you pick out what the base is.

0
same doubt what to take base here?
+3 votes

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

When we represent nk/2 and nk 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 ??

by Boss (10.8k points)
0
If it's base n, then it's correct. But here base is not given.
+3
We can convert the number to base n in O(n) time.

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
checking all buckets?

what is this , I have not read anything like that in CLRS ?
+1

@VS ji,

Please refer -->

Here we have 10 buckets.

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

–1
Source?
+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=logbnk as no.s in range nk/2 to nk

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

Anything wrong above?

0

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

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

by Active (4.3k points)
edited by
0

@Nitesh Singh 2

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

0
I think both are different. m is the base of the number representation and k determines the range in which those n values lies.
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

by Loyal (6.7k points)
Answer:

Related questions

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
50,737 questions
57,362 answers
198,491 comments
105,260 users