a) (5Marks) Arrange the following in the least to most complexity order. Here n
ID: 3610683 • Letter: A
Question
a) (5Marks)
Arrange the following in the least to mostcomplexity order. Here n is the input size for the somecomplexity function and k< j and j & k are numbersgreater than1.
,2n
b) (10 Marks)
Carry out the radix sort on the following four digitsnumbers and also develop
complexity function and then write worstcaseTheta Qnotation for the radix sortalgorithm .
4141,1545,1178,1196,2133,2122,3122,3111,1122,2210
Explanation / Answer
//Hope this will help you.//Don't forget to rate it.
1.
1 < nlgn < n < nk< nj <2n < kn < jn < n!
2.
Round 1
[0]=2210
[1]=4141 3111
[2]=2122 3122 1122
[3]=2133
[4]=
[5]=1545
[6]=1196
[7]=
[8]=1178
[9]=
Round 2
[0]=
[1]=2210 3111
[2]=2122 3122 1122
[3]=2133
[4]=4141 1545
[5]=
[6]=
[7]=1178
[8]=
[9]=1196
Round 3
[0]=
[1]=3111 2122 3122 1122 2133 4141 1178 1196
[2]=2210
[3]=
[4]=
[5]=1545
[6]=
[7]=
[8]=
[9]=
Round 4
[0]=
[1]=1122 1178 1196 1545
[2]=2122 2133 2210
[3]=3111 3122
[4]=4141
[5]=
[6]=
[7]=
[8]=
[9]=
So finaly it will be:
1122
1178
1196
1545
2122
2133
2210
3111
3122
4141 The timecomplexity of the algorithm is as follows:
Suppose that the n input numbers have maximum k digits.
Then the Counting Sort procedure is called a total of k times.
Counting Sort is a linear, or O(n) algorithm.
So the entire Radix Sort procedure takes O(kn) time.
If the numbers are of finite size, the algorithm runs in O(n)asymptotic time.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.