Description: The following is an algorithm called DumbSort(A[N]): find the range
ID: 3596628 • Letter: D
Question
Description: The following is an algorithm called DumbSort(A[N]): find the range R of the array A. This can be done by taking the highest number h-lowest number w in A Create an array A_new[R+1] initialized to 0. For each element e in A[N], increment the value at A_new[e w] For each index i of the resulting A_new[R] array; write the number w+i into array A, A_new[i] times. 1. 2. For example, in the array A = [3, 11, 9, 5, 2, 5], the highest number h = 11, lowest number w and range R = 11-2-9. we will create an array A-new[10] . Resulting in a A-new- [1,1,0,2,0,0,0,1,0,1]. Finally, A will be rewritten as A = [2,3,5, 5, 9, 11]. 2, Task: ) Analyze DumbSort for its running time. What is the big-O of the new algorithm? (clearly indicate the input size of this problem). Please include an (English) argument with your conclusion. Why should we never discuss this algorithm again? (ii)Explanation / Answer
Answer:
a. given n = number of list elements, r = range of list
total big O is O(n) + O(r)
i. It is O(n) , if n > r
ii. O(r), if r > n
b. This algorithm depends on range of elements, say we have range of 10000 and
2 elements it will have a big-o of O(r). It is not a good idea to use aglos that
scale with the magnitude of list elements.
If this answer was helpful please Like / Vote Thumbs up!