3. Recursion

The Process

• Divide the problem into sub-problems
  • Usually $(1, n-1)$ or ($\frac{n}{2}, \frac{n}{2})$
• Solve the sub-problems
• Merge the sub-problems

Example: Merge Sort

Merge sort from left to middle, merge sort from middle to right and then merge the results:

• Divide: find the middle element
• Solve: merge sort the two sub-arrays
• Merge: mere the two sub-arrays

The base case is when the length of the array is 0 or 1.

Analysis

For $T(n)$, the cost will be either the base case of $\Theta(1)$, or the sum of:

• Subdivision: $\Theta(1)$ to find the center
• Solving sub-problems: $2T(\frac{n}{2})$
• Merge: $\Theta(n)$

At each level, the cost will be:

There are $\log_2{n}$ levels, so the total cost is $n\log_2n$.