def Merge(arr, p, q, r):
inversion_count =0
n_L = q - p + 1 # length of arr[p:q]
n_R = r - q # length of arr[q+1:r]
L, R = [], [] # new lists
L = arr[p:q+1]
R = arr[q+1:r+1]
i, j, k = 0, 0, p
while i < len(L) and j < len(R):
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
inversion_count += (q-i+1) # keeps track of the number of inversions between left and right arrays
j += 1
k += 1
# having gone through one of L and R entirely,
# copy the remainder of the other to the end of arr[p:r]
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
return inversion_count
def MergeSort(A,p,r):
inversion_count = 0
# Base case
if p>=r :
return 0
# Recursive case
q = (p+r)//2
inversion_count += MergeSort(A,p,q)
inversion_count += MergeSort(A,q+1,r)
inversion_count += Merge(A,p,q,r)
return inversion_countHomework 3
Download the corresponding ipynb file here: hw-3.ipynb.
Recursive Insertion Sort
You can also think of insertion sort as a recursive algorithm (recInsertionSort). In order to sort A[0:n-1]: - recursively sort the subarray A[0:n-2] and then - insert A[n-1] into the sorted subarray A[0:n-2].
Exercise 1 (5 Points) Write a Python code for this recursive version (recInsertionSort) of insertion sort.
Exercise 2 (3 Points) Give a recurrence equation for its worst-case running time T(n).
Exercise 3 (2 Points) Compare and contrast T(n) with the best and worst-case running times of incremental insertionSort.
Divide-and-Conquer
Exercise 4 (3 points) Let A[0:n-1] be an array of n numbers. If i<j and A[i]>A[j], then the pair (i,j) is called an inversion of A.
Design an \mathcal O(n\lg{n}) algorithm that determines the number of inversions in any permutation of n elements. Provide a Python implementation.
Hint: Modify MERGE-SORT.
Exercise 5 (2 points) Analyze the time complexity of your algorithm in Exercise 4.
Solution. Note that the MERGE algorithm executes the else block (line #18) whenever it reaches an inversion (i,j). Indeed, all the (q-i+1) pairs \{(i',j)\mid i'=i,i+1,\ldots,q\} are also inversions of A.
So, our strategy here is to sort A recursively using MERGE-SORT as before—but with a modified MERGE routine. The modified MERGE will keep a counter (inversion_counter) and increment it by q-i+1 whenever the above mentioned block is executed.
Here is a detailed solution by one of our students.
Solution by Keerthana Aravindan
The following recursive algorithm determines the number of inversions in an array A[0:n-1] representing a permutation of n elements using a divide-and-conquer strategy:
Divide: divide the subarray A[p:r] into two adjacent subarrays, each nearly half the size. This division involves computing the midpoint q of A[p:r] by averaging p and r, and subsequently splitting A[p:r] into subarrays A[p:q] and A[q+1:r].
Conquer: during sorting each of the two subarrays A[p:q] and A[q+1:r] recursively using MERGE-SORT, count the number of inversions where an element in the left subarray is greater than an element in the right subarray. Base case: when the subarray to be sorted has just 1 element, that is, when p\geq r.
Combine: by merging (MERGE) the two sorted subarrays A[p:q] and A[q+1:r] back into A[p:r], determine the number of inversions while performing the merge operation.
Create two indices i and j, where i corresponds to the first half, and j to the second half. If an element A[i] > A[j], then there will be (mid – i) inversions as all the remaining elements in left-subarray (A[i+1], A[i+2],\ldots,A[mid]) will be greater than A[j].
Similar counter to the MERGE-SORT procedure is used to sum up the number of inversions from the recursive calls, as well as from the call to the modified MERGE function.
After copying A[p,\ldots,q] to L and A[q + 1,\ldots,r] to R in MERGE. Lets consider an element a in L[i] and b in R[j] . During MERGE-SORT invoked for the array A, at some point in a call to MERGE, a>b having i < j happens. Since the arrays L and R are sorted, there will be merge-inversions involving b and L[i], L[i + 1], L[i + 2],\ldots, L[q], as these produces (q − i + 1) merge-inversions with only ones involving b.
Once b is copied back to A, it will share the same merged subarray with the elements in L[i:n_L-1], Thus inversion is not counted twice in subsequent recursive calls to ‘Merge’ and while loop in MERGE.
Runtime: The runtime is the same as that of MERGE-SORT because only an additional constant-time operation is added to some of the iterations of the loops.
Since MERGE is \mathcal O(n\lg n), so is this algorithm running time also sums up to O(n\lg n).
Python Implementation
Exercise 6 (3 points) Design an \mathcal{O}(n\lg{n}) algorithm that, given a set S of n integers and another integer x, determines whether S contains two elements that sum to exactly x. Provide a Python implementation.
Solution. The procedure below is not recursive in itself, however it uses the recursive MERGE-SORT and BIN-SEARCH subroutines.
\begin{algorithm} \caption{FindPairWithSum} \begin{algorithmic} \Procedure{FindPairWithSum}{$A[0:n-1], x$} \State{\Call{MergeSort}{$A$}} \For{$i=0$ to $n-2$} \State{$y=x-A[i]$} \State{$id= $\Call{BinSearch}{$A[i+1,n-1], y$}} \If{$id\neq -1$} \Return{$True$} \EndIf \EndFor \Return{$False$} \EndProcedure \end{algorithmic} \end{algorithm}
Runtime: The total cost is sum of the following two contributions:
line
#2takes \mathcal O(n\lg{n})for each i=0,\ldots,n-2, line
#5takes about O(\lg{(n-i-1)}) or c_1\lg{(n-i-1)}. Adding them up gives us: c_1\sum_{i=0}^{n-2}\lg{(n-i-1)}=c_1\lg\left(\prod_{i=0}^{n-2}(n-i-1)\right) =c_1\lg{(n-1)!}. Note that (n-1)!\leq n^n for any n\geq1. Since \lg is an increasing function, from the above equation we have c_1\sum_{i=0}^{n-2}\lg{(n-i-1)}\leq c_1\lg{n^n}=c_1n\lg{n}. So, the for loop takes a total of O(n\lg{n}) time.
Hence, the running time T(n)=O(n\lg{n}).
Also, check out the following student submission.
Detailed Explanation by Keerthana Aravindan
The following algorithm determines whether the set S contains 2 elements that sum to exactly x :
Let S be represented as an array A[0:n-1].
Target = x ( sum of 2 elements)
First, A is sorted using merge sort, so that binary search for (target – A[i]), where i ranges from 0 to n-2 can be performed.
Then A is traversed in sorted order. For each element A[i], binary search in the subarray A[i+1:n-1] is performed to find another element that, when added to A[i], yields the target sum x.
The search for last element is already checked during i=n-2, thus final element search can be skipped.
The procedure can be terminated once A[i] > x/2 as all elements in the subarray A[i+1:n-1] will be greater than x/2, and the search will never succeed.
Depending on the search result, the algorithm returns either True or False as result.
Both Merge sort and binary search are implemented using the Divide and conquer recursive algorithm.
Sorting the array A[0:n-1] using merge sort takes O(n\lg n) running time.
Binary search running time is O(\lg n). The Binary Search procedure is called at most n-2 times, for subarrays of increasing sizes from i+1 to n-1.
Therefore, the total time spent in all these calls won’t exceed n.O(\lg n).
Exercise 7 (2 points) Analyze the time complexity of your algorithm in Exercise 6.
Time-complexity of Recursive Algorithms
Exercise 8 (1 point) Use the Master Theorem to get an upper bound (in big-\mathcal O notation) for the following recursion: T(n)=T(n/2) + n^3.
Solution
If I use Master Theorem to verify the answer in the exercise 2, I have to distinguish what are a, b, k.
Based on the equation T(n) of the exercise 2:
a = 1 b = 2 k = 3
Therefore,
b^k = 2^3 = 8
Because, a < b^k, we get T(n) = O(n^3).
Exercise 9 (1 point) Use the Master Theorem to get an upper bound (in big-\mathcal O notation) for the following recursion: T(n)=4T(n/2) + n.
Solution.
Exercise 10 (3 points) Given the recurrence relation T(n)=2T(n/2)+\mathcal O(n), what is the time complexity of the corresponding recursive algorithm?
Exercise 11 (🏅 Bonus) How does recursion impact space complexity, and what factors should be considered when analyzing it?