Some basic information for solving assignment question is givenbelow. Growth Rat
ID: 3610593 • Letter: S
Question
Some basic information for solving assignment question is givenbelow.
Growth Rate of Function:
If some function f1(x)>f2(x) forpositive values of x then the function f1(x) is said tohave greater growth rate then f2(x). For examplef1(x)=x4 and f2(x)=x3 it is obvious that f1(x) has greatergrowth rate ( 24 > 23).This concept relateto complexity of algorithm ,an algorithm having greater growth ratefunction means the algorithm has greater complexity heref1(x) is more complex then f2(x).
EstimatedTime 1.5 hour
For part “a”maximum time is 30 minutes and for part “b” maximumtime is one hour. It all depends upon your sheerconcentration.
Question (5+10)
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.
b) (10 Marks)
Carry out the radix sort on the following four digitsnumbers and also develop
complexity function and then write worst caseTheta Q notation for the radix sort algorithm .
4141,1545,1178,1196,2133,2122,3122,3111,1122,2210
Explanation / Answer
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
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.