b) Write down the recurrence relation of the following sorting algorithm. What is the time complexity...

Transcribed Image Text:

b) Write down the recurrence relation of the following sorting algorithm. What is the time complexity of this method (in O(-) notation)? Justify your answer. Does this algorithm sort properly? Give an explanation if you think it does. Give a counterexample showing that it fails to sort if you think it doesn't. [10 pt] void StrangeSort (int a[], int min, int max) { if (minmax) return; if (a[min] a [max]) swap (a[min], a[max]); // constant-time operation int one third = (max) min + 1) / 3; if (one third >= 1) { StrangeSort (a[], min, max - one_third); Strangesort (aj, min + one_third, max) Strangesort (aj, min, max- one_third); } } b) Write down the recurrence relation of the following sorting algorithm. What is the time complexity of this method (in O(-) notation)? Justify your answer. Does this algorithm sort properly? Give an explanation if you think it does. Give a counterexample showing that it fails to sort if you think it doesn't. [10 pt] void StrangeSort (int a[], int min, int max) { if (minmax) return; if (a[min] a [max]) swap (a[min], a[max]); // constant-time operation int one third = (max) min + 1) / 3; if (one third >= 1) { StrangeSort (a[], min, max - one_third); Strangesort (aj, min + one_third, max) Strangesort (aj, min, max- one_third); } }

Answer rating: 100% (QA)

The recurrence relation for the given sorting algorithm StrangeSort can be expressed as follows Tn Tn3 T2n3 O1 Where Tn represents the time taken to s... View the full answer