Mergesort sorts a list by dividing it into two equal parts, sorting each half by recursion, then combining resulting sorted components. The recurrence relation for mergesort is T(n) ⇐ 2T(n/2) + cn when n>2 and T(2) ⇐ c. There are two ways to solve the recurrence relation: unrolling the recursion and substituting a solution. Unrolling the recurrence includes analyzing the first few levels, identifying a level pattern, and sum over all levels of recursive calls. Substituting requires you to is where you guess the solution, substitute it in, and prove that it works. The total runtime of mergesort is O(nlogn).

• Mergesort sorts a given list of numbers by first dividing them into two equal halves, sorting each half separately by recursion, and then combining the results of these recursive calls, in the form of two sorted halves, using the linear time algorithm for merging sorted lists.
• Template for Divide and Conquer Algorithms
  • Divide the input into two pieces of equal size; solve the two subproblems on these pieces separately by recursion; and then combine the two results into an overall solution, spending only linear time for the initial division and final recombining.
• Base case for recursion: once the input has been reduced to size 2, we stop the recursion and sort the two elements by simply comparing them to each other
• T(n) denotes its worst case runtime of the template above, O(n) time to divide the input into two pieces, spends T(n/2) to solve each one, O(n) to recombine the solutions from the two recursive calls; runtime T(n) solves following recurrence relation
  • T(n) ⇐ 2T(n/2) + cn when n>2; T(2) ⇐ c
• The recurrence relation does not explicitly provide an asymptotic bound on the growth rate of the function T; rather, it specifies T(n) implicitly in terms of its values on smaller inputs.
• To obtain an explicit bound, need to solve the recurrence relation.

• Unroll the recursion: accounting for the runtime across the first few levels, and identify a pattern that can be continued as the recursion expands; then, sum the runtime once all the levels of the recursion to arrive a total runtime
• Substituting a solution: guess for the solution, substitute it into the recurrence relation, check if it works

• Analyze the first few levels
  • First level: single problem of size n takes at most cn time plus subsequent recursive calls
  • Second level: two problems size n/2 each takes time cn/2 (sum of cn) plus subsequent recursive calls
  • Third level: four problems of size n/4 each takes time cn/4 (total cn)
• Identify a pattern
  • At level j of recursion, number of subproblems doubled j times (now a total of 2^j). Each subproblem has shrunk size by factor of two j times (each size n/2^j so each takes timecn/2^j).
  • Level j total runtime: 2^j(cn/2^j) = cn
• Sum over all levels of recursion
  • Number of times the input must be halved in order to reduce its size from n to 2 is log2(n)
  • Total runtime: O(nlogn)

• T(n) is bounded by O(nlogn); we have agues for the runtime that we want to verify
• T(n) ⇐cnlog2(n) for all n>= 2
  • Base case: holds for n = 2
  • By induction, T(m) ⇐ cmlog2(m) for all values of m less than n
  • Want to establish this for T(n)
    • T(n) ⇐ 2T(n/2) + cn ⇐ 2c(n/2)log2(n/2) + cn = cn[log2(n) – 1] + cn = cnlog2(n) – cn + cn = cnlog2(n)
    • This establishes what we want for T(n)

• Somewhat weaker kind of substitution one can do, in which guesses the overall form of the solution without pinning down the exact values of all the constant and other parameters at the outset
• Method can actually be useful in working out the exact constant when one has some guesses of the general form of the solution

At first, the concept of unrolling a recurrence was difficult for me to grasp. However, now, it is easy to see that you just see the number of problems on each level, the size of each problem, and the time cost of each problem on the level. Once you add them all up and are able to generalize a level rule, then you just have to think about how many times the recursion can occur, then you're done! You have a runtime.

On a scale of 1 to 10, the readability of this section is an 8. The only reason this is not a 10 is that at first, unrolling was a difficult concept for me to grasp. However, now, after seeing unrolling in class a few times and reading all of the sections for this reading, unrolling makes a lot of sense now. It was a really great idea for the authors to unroll an algorithm that we already knew the runtime of and knew how it worked.

Now, we need to consider divide and conquer algorithms that create recursive calls on q subproblems of size n/2 and comibine the results in linear time. We already handled when q=2 with mergesort. When q > 2, the recurrence relation is T(n) ⇐ qT(n/2) + cn when n > 2 and T(2) ⇐c. By unrolling the recursion, we come to the conclusion that the runtime of the algorithm is O(n^(log2q)). When q = 1, by unrolling the recurrence, we get that T(n) ⇐ 2cn = O(n). A related recurrence of T(n) ⇐2T(n/2) +cn^2 when n > 2 and T(2) ⇐ c has a runtime of O(n^2), which we see by unrolling the recurrence.

• More general class of algorithms is obtained by considering divide-and-conquer algorithms that create recursive calls on q subproblems of size n/2 and then comibine the results in O(n) time
• If T(n) denotes the runtime of an algorithm designed in this style, then T(n) obeys the following recurrence relation
  • T(n) ⇐ qT(n/2) + cn when n > 2; T(2) ⇐c
• Unroll the recursion
• Analyzing the first few levels
  • First level: one problem of size n, cn time
  • Second level: q problems of size n/2, each cn/2 time (total qcn/2)
  • Third level: q^2 problems of size n/4, total time (q^2/4)cn
  • Work per level is increasing as we recurse
• Identifying a pattern
  • Level j is q^j(c/2^j) = (q/2)^jcn
• Summing over all levels of recursion
  • Log2n levels of recursion
  • Get a geometric sum whose solution is O(n^(log2q))
• Running time is more than linear but still polynomial in n

• q = 1
• Unroll the recursion
• Analyzing the first few levels
  • First level: one problem of size n, cn time
  • Second level: one problem of size n/2, cn/2 time
  • Third level: one problems of size n/4, total time cn/4
  • Work per level is decreasing as we recurse
• Identifying a pattern
  • Level j is one instance at size n/2^j, so runtime is cn/2^j
• Summing over all levels of recursion
  • Log2n levels of recursion
  • Get a geometric sum whose solution is T(n) ⇐ 2cn = O(n)
• Geometric series with a decaying exponent is a powerful thing: fully half the work performed by the algorithm is being done at the top level of recursion
• When q = 1, runtime is linear; when q = 2, runtime is O(nlogn); when q > 2, runtime is polynomial bound with an exponent larger than 1 that grows with q.
• When q = 1, the total runtime is dominated by the top level, whereas when q > 2 runtime is dominated by the work done on constant-size subproblems at the bottom of the recursion.

• Recurrence is based on the following divide and conquer structure:
  • Divide the input in to two pieces of equal size; solve the two subproblems on these pieces separately by recursion; and then combine the two results into an overall solution, spending quadratic time for the initial division and final recombining.
• T(n) ⇐2T(n/2) +cn^2 when n > 2; T(2) ⇐ c
• Unroll the Recurrence
• Analyzing the first few levels
  • First level: one problem of size n, cn^2 time
  • Second level: two problems of size n/2, each c(n/2)^2 time (total time of cn^2/2)
  • Third level: four problems of size n/4, each c(n/4)^2 time cn/4 (total time of cn^2/4)
  • Work per level is decreasing as we recurse
• Identifying a pattern
  • Level j is 2^j subproblems at size n/2^j, so runtime is cn^2/2^j
• Summing over all levels of recursion
  • Similar sum to q = 1 case
  • Log2n levels of recursion
  • Get a geometric sum whose solution is T(n) ⇐ 2cn^2 = O(n^2)

• Under what conditions would this recurrence T(n) ⇐ 2T(n/2) + O(n^2) happen? Do you have an example algorithm that has this recurrence equation?

At first, I was confused on why the general q>2 subproblems still had log2n recurrences, but now I understand. The number of problems are the different than in mergesort, but the size of each problem is spilt in half on each call of the recursion like with mergesort. Therefore, there would still have the be log2n levels. It is not dependent on the number of problems; it is dependent on the size of the problem.

On a scale of 1 to 10, the readability of this section was a 9. The progression of the general solution of what was discussed in the previous chapter to the special cases of q = 1 was a really great structuring on the authors' part. They really knew the most natural progression of information and presented it in a way that was clear and easy to understand. Another thing that helped is that there aren't a bunch of really long proofs with new notation, which are sometimes hard to comprehend.

We want to be able to tell how far away a list is from being in order. In order to do this, we just have to count the number of inversions. The brute force solution to the algorithm runs in O(n^2) time, but we can do better than that. We will divide the list in half, count the number of inversions in each piece, and make the algorithm recursively sort the two halves. Once we get the two sorted halves, we want to combine them into a single sorted list while counting the number of inversions as we go. The Merge-and-Count routine takes O(n) time and the Sort-and-Count algorithm takes a total O(nlogn) time.

• Core issue is the problem of comparing two rankings
• Want to define a measure that tells us how far this list is from being in ascending order
• Natural way to qualify this notion is by counting the number of inversion
• When sequence is in ascending order, there are no inversions
• When sequence is in descending order, every pair forms an inversion, so there are C(n, 2) inversions (“n choose 2”)

• Brute force: we could look at every pair of numbers (ai, aj) and determine whether they constitute an inversion, O(n^2) runtime
• Our goal is to count the inversions in O(nlogn) time
• Divide the list into two pieces, count the number of inversions (ai, aj) where the two numbers belong to different halves in O(n) time, make the algorithm recursively sort the numbers in the two halves
• Crucial routine: Merge-and-Count
  • After recursively sorting the two halves of the list and counter the inversions in each, now have two sorted lists A and B. We want to produce a single sorted list C from their union, while counting the number of pairs (a, b) with a in set A, b in set B, and a>b.
  • Walk through the sorted lists A and B, removing elements from the front and appending them to sorted list C
  • In a given step, we have a Current pointer into each list showing our current position. Compare the elements ai and bj being pointed to in each list, remove the smaller one form its list and append it to the end of C.
  • Every time the element ai is appended to C no inversions are encountered, since ai is smaller than everything left in list B and it comes before all of them.
  • If bj is appended to list C, then it is smaller than all the remaining items in A and it comes after all of them, so we increase our count of the number of inversions by the number of elements remaining in A.

   Merge-and-Count(A, B)
        Maintain a current pointer into each list, initialize to point to the front elements
        Maintain a variable Count for the number of inversion, initialized to 0
        While both lists are nonempty:
             Let ai and bj be the elements pointed to by the Current pointer
             Append the smaller of these two to the output list
             If bj is the smaller element:
                  Increment Count by the number of elements remaining in A
             Endif
             Advance the Current pointer in the list from which the smaller element was selected
        Endwhile
        Once one list is empty, append the remainder of the other list to the output
        Return Count and the merged list

• Each iteration of the while loop takes constant time and number of iterations can be done at most the sum of the initial lengths of A and B, so the total runtime is O(n)

   Sort-and-Count(L)
        If the list has one element:
             There are no inversions
        Else:
             Divide the list into two halves:
                  A contains the first half of the elements (ceiling of n/2)
                  B contains the remaining elements (floor of n/2)
             (rA, A) = Sort-and-Count(A)
             (rB, B) = Sort-and-Count(B)
             (r, L) = Merge-and-Count(A, B)
        Endif
        Return r = rA + rB + r, and the sorted list L

• Merge-and-Count procedure takes O(n) time, the running time T(n) of the full Sort-and-Count procedure satisfies the recurrence
• The Sort-and-Count Algorithm correctly sorts the input list and counts the number of inversions: it runs in O(nlogn) time for a list with n elements.

At first, I was confused on exactly how we were counting the inversions by sorting. Later, it became clear. In the Merge-and-Count list merges the two sorted lists together and if an element in the second list (which was later in the ordering) comes before elements in the first list, you increment the inversion count by the number of elements left in the first list. Inversions are also counted when the two separate lists in divide and conquer are sorted.

On a scale of 1 to 10, the readability of this section was an 8. We had already learned about inversions before this section in regards to exchange arguments, so the problem was easy to comprehend, and the solution was very clever but once they told us what it was, it was not difficult to comprehend. It kind of built off mergesort, which is what we learned about in the first section.