Chapter 5

Sorry the comments have to come first, can't help it. TOO EXCITED! So this is how I view Divide and Conquer:

“Breaking a bundle of sticks into two halves is hard, but it is easier to break each of the sticks and then binding them together.” - Every time I think of the phrase “Divide and Conquer”.

“I'd rather kill each of the guards one by one stealthily than go jump in the middle of 10 guards and fight everyone at the same time.” - My view while playing Assassin's Creed.

“I prepare notes on the even numbered chapters and you prepare the notes for the odd numbered ones, and we share at the end.” - A conversation with one of my fraternity brothers, who is in the same Finance class as me.

Intuition: Divide the data into two halves, solve each part by recursion, then combine the two results to get the overall solution.

In mergesort, we need a base case so that we know when to stop dividing our data set and start returning a combined solution of the two parts. The runtime T(n) satisfies the following recurrence relation:

   For some constant c, 
        T(n) <= 2T(n/2) + cn
   when n>2, and
        T(2) <= c
        

This can also be written as T(n) ⇐ 2T(n/2) + O(n), suppressing the constant c.

• Unroll the recursion: Check the runtime for the first few levels and find a pattern that can be continued as the recursion expands. Then, sum it up.
• Trial and error: Guess the solution, try it out and check if it works.

* Analyzing the first few levels: