This is the 3rd time I am asking for the same question and nobody reads the hint

Question

This is the 3rd time I am asking for the same question and nobody reads the hint, please you must use it!

Q: Find the time complexity of the following radix sort pseudo code. Show all your work.

Hint: Your solution must start from T(n) = O( d(n+k) ) and ends with T(n) = O(n) as d=constant & k=O(n). "In other words, You must prove that T(n) = O(d(n+k)) =...until T(n) = O(n) "

RADIX-SORT (A, d) 1 for i 1 to d 2 n-AA length 3 exp 10A(i-1) Use bubble sort(stable sort) to sort array A on digit i 4 for j 1 to n for k j+1 to n if (AU]/exp) mod 10 (A[k/exp) mod 10 exchange A il with AU]

Explanation / Answer

1.for i=1 to d

this line executed in 1 unit of time.

3.exp=10^(i-1)

this line time complexity depends on the value "i" which is given

In exponnetial radix sort or (ant type of sort takes) [T(n)=2^n]

but we are using radix sort so T(n)=O(n)

so overall time complexity of the given program is T(n)=n.2^n

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.