Consider the pseudo-code of the following sorting algorithm. 1 silly sort (ARRAY): 2 if length (ARRAY)...

Transcribed Image Text:

Consider the pseudo-code of the following sorting algorithm. 1 silly sort (ARRAY): 2 if length (ARRAY) < 2: for (i from 0 to length (ARRAY) - 1): array copy (ARRAY) 3 done 4 else: 5 6 7 8 9 10 11 12 13 swap array [0] and array[i] maybe sorted array [0] concatenated to silly sort (array[1..end]) for (i from 0 to length (maybe sorted) - 2): if maybe sorted [1] COMPARE GREATER THAN maybe sorted [i + 1]: break if did not break out of for: return maybe sorted Let's assume that the comparison in line 10 is invoked for every i in line 9 and denote by T(n) the number of times COMPARE GREATER THAN is peformed when silly sort is executed on an array of n numbers (thus T(n) is an upper bound for the actual number of comparisons). 1. The code above indicates that 7(1) = 0. Give a recurrence equation for T(n) 2. Show by induction that for n 3, 7(n) 2n! 3. *Extra Credit: Show by induction that for n 2, T(n) 3n! Consider the pseudo-code of the following sorting algorithm. 1 silly sort (ARRAY): 2 if length (ARRAY) < 2: for (i from 0 to length (ARRAY) - 1): array copy (ARRAY) 3 done 4 else: 5 6 7 8 9 10 11 12 13 swap array [0] and array[i] maybe sorted array [0] concatenated to silly sort (array[1..end]) for (i from 0 to length (maybe sorted) - 2): if maybe sorted [1] COMPARE GREATER THAN maybe sorted [i + 1]: break if did not break out of for: return maybe sorted Let's assume that the comparison in line 10 is invoked for every i in line 9 and denote by T(n) the number of times COMPARE GREATER THAN is peformed when silly sort is executed on an array of n numbers (thus T(n) is an upper bound for the actual number of comparisons). 1. The code above indicates that 7(1) = 0. Give a recurrence equation for T(n) 2. Show by induction that for n 3, 7(n) 2n! 3. *Extra Credit: Show by induction that for n 2, T(n) 3n!

Answer rating: 100% (QA)

1 Recurrence equation for Tn From the given pseudocode the number of comparisons Tn is based on the ... View the full answer