(a) Given the following list of numbers: 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 trace t
ID: 3854731 • Letter: #
Question
(a) Given the following list of numbers:
3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5
trace the execution for quicksort with median-of-three partitioning and a cutoff of 3.
(b) The processing time of an algorithm is described by the following recurrence equation (c is a positive constant):
T(n) = 3T(n/3) + 2cn; T(1) = 0
What is the running time complexity of this algorithm? Justify.
(c) You decided to improve insertion sort by using binary search to find the position p where the new insertion should take place.
What is the worst-case complexity of your improved insertion sort if you take account of only the comparisons made by the binary search?
What is the worst-case complexity of your improved insertion sort if only swaps/inversions of the data values are taken into account?
Explanation / Answer
1. Sort 3, 1, 4, 1, 5, 9, 2, 6, 5 using quick sort.
Input
3
1
4
1
5
9
2
6
5
i=0
*3
1
4
1
5
9
2
6
5
i=1
3
1*
4
1
5
9
2
6
5
Insert
1
3
4
1
5
9
2
6
5
i=2
1
3
*4
1
5
9
2
6
5
i=3
1
3
4
*1
5
9
2
6
5
Insert
1
1
3
4
5
9
2
6
5
i=4
1
1
3
4
*5
9
2
6
5
i=5
1
1
3
4
5
*9
2
6
5
i=6
1
1
3
4
5
9
*2
6
5
Insert
1
1
2
3
4
5
9
6
5
i=7
1
1
2
3
4
5
9
*6
5
Insert
1
1
2
3
4
5
6
9
5
i=8
1
1
2
3
4
5
6
9
*5
1
1
2
3
4
5
5
6
9
2. T(n) = 3T(n/3) + 2cn ------> 2cn
3T(n/3)=3(3T(n/9) +2/3cn) --------> 2cn
Hence, we get the time complexity pattern as:
2cn+2cn+2cn.......k times
now 3T(n/3k)=3T(1)
n/3k=1
3k=n
k=log3(n)
Hence time complexity = (k times) 2cn + 2cn + 2cn....
= k*2cn
=2c*k*n
=O(k*n)
=O(log3(n)*n)
3. If the cost of comparisons exceeds the cost of swaps, as is the case for example with string keys stored by reference or with human interaction (such as choosing one of a pair displayed side-by-side), then using binary insertion sort may yield better performance. Binary insertion sort employs a binary search to determine the correct location to insert new elements, and therefore performs log2(n) comparisons in the worst case, which is O(n log n). The algorithm as a whole still has a running time of O(n2) on average because of the series of swaps required for each insertion.
1. Sort 3, 1, 4, 1, 5, 9, 2, 6, 5 using quick sort.
Input
3
1
4
1
5
9
2
6
5
i=0
*3
1
4
1
5
9
2
6
5
i=1
3
1*
4
1
5
9
2
6
5
Insert
1
3
4
1
5
9
2
6
5
i=2
1
3
*4
1
5
9
2
6
5
i=3
1
3
4
*1
5
9
2
6
5
Insert
1
1
3
4
5
9
2
6
5
i=4
1
1
3
4
*5
9
2
6
5
i=5
1
1
3
4
5
*9
2
6
5
i=6
1
1
3
4
5
9
*2
6
5
Insert
1
1
2
3
4
5
9
6
5
i=7
1
1
2
3
4
5
9
*6
5
Insert
1
1
2
3
4
5
6
9
5
i=8
1
1
2
3
4
5
6
9
*5
1
1
2
3
4
5
5
6
9
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.