The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
1k views

If there are n integers to sort, each integer had d digits and each digit is in the set {1, 2, ...., k}, radix sort can sort the numbers in

  1. O(d n k)
  2. O(d n$^k$)
  3. O(d+n)k)
  4. O(d(n+k))
in Algorithms by Veteran (103k points)
recategorized by | 1k views
0

1 Answer

+1 vote

http://lcm.csa.iisc.ernet.in/dsa/node210.html

Look at the above link on how algo works.

Lets consider there are 'K' buckets (as given).

Now, for each digit you repeat the following:

1) place the digit of each number in the appropriate bin.  -  ø($n$)

2) append all the 'K' bins sequentially.

Thus, for a single digit, its ø($n + k$),

For 'd' digits, its ø($d(n + k)$)

by Boss (18.3k points)
0
It should be n*k for a single digit as single digit is compared with k bins for placement. and for d digits it should be total n*k*d i dont understand why n+k is there??
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,362 questions
55,786 answers
192,411 comments
90,919 users