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

edited | 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}$

@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

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.

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$

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

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?

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.

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

by Boss (10.9k 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.

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,

Here we have 10 buckets.

–1
Source?
+3

What I got :

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)

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

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 (7k points)