Q1
How does selecting a pivot make a difference in the time complexity of Quick Sort algorithm? What kind of pivot should be avoided? Explain why.
The pivot chosen in quick sort determines the size of the subsequent divided arrays. Since we want our algorithm to run efficiently, we would optimally want the sub-arrays to be equal in size. To make this happen, we would want to choose a pivot number that is the median of the array, and not a number that is the largest or smallest of the array.
Because of this, if the pivot is chosen is the first or last element, a pathological case occurs where the algorithm becomes O(n^2) on sorted input. The easiest way to fix this is to choose a random element for the pivot on each iteration, making it impossible to create a pathological data set for the algorithm.
Q2
Use the Master theorem to compute the theta bound for Quick Sort algorithm when the pivot gives balanced partitions.
If pivots are chosen pathologically:
Quicksort algorithm complexity (assuming pivots split input into rougly equal subproblems):
Solving using master theorem:
- a=2, b=2, c=1
, therefore our algorithm is
Q3
Explain the steps taken in the slide 26 to compute the Time Complexity (i.e., T(n) ) of recursively reversing a sequence.
1 int[] reverse(int[] data, int low. int high) {
2 if(low>high) return data; # O(1)
3 swap(data[low],data[high]); # O(1)
4 return reverse(data, ++low,--high); # T(n-2)
5 }
The algorithm runtime is defined as follows:
Going through the steps of the algorithm line by line:
- Function definition, accepts an array and 2 array indices. This tracks our ‘progress’ through the array between recursive calls.
- The base case, if our indices cross we return the data, having swapped the entire array
- The swap, we switch the data contained at the target indices
- The recursive call, we continue our reversing on a subarray, with a low index one higher and a high index one lower.
Q4
In the multiplication problem, assume that the operands x and y are represented in base-2 . We want to obtain x.y = ? (Example : x = 1100 , y = 1101 ) . Using the following equation, answer the questions below.
x1 : corresponds to the lower-significant n/2 bits of x
x0: corresponds to the higher-significant n/2 bits of x n: we assume that n is even in this case.
Part 1)
Based on the number of subproblems above, compute T(n) and the theta bound for it. You can use the replacement strategy or Master Theorem. Explain your approach and provide your work.
The runtime for the algorithm would be
Analyzing theta bound using master theorem:
- a=4,b=2,c=1
, therefore
Part 2)
Is there a way to reduce the time complexity similar to the optimization strategy discussed in lecture 4? Provide a comprehensive and detailed mathematical work.
Yes, we can reduce the time complexity by reducing the number of multiplications (sub-problems) performed on each recursive step. This is done by combining the two middle terms into one term, r.
Derivation,
: the upper n/2 bits of x/y : the lower n/2 bits of x/y
Using this formula, there’s only three unique multiplications to compute:
Our new formula for the multiplication recurrence is:
Analyzing using the master theorem, we find that our new recurrence has a theta bound of