91Ó°ÊÓ

The Master Theorem is a crucial concept for analyzing recurrence relations of the form \( T(n) = aT(n/b) + f(n) \). It provides a means to determine the asymptotic behavior or the bounding function for a recurrence equation, making it easier to understand the growth of algorithms. There are three main cases to consider when applying the Master Theorem, and each relates to comparing the function \( f(n) \) with \( n^{\log_b a} \):

• **Case 1:** If \( f(n) \) is \( O(n^{c}) \) where \( c < \log_b a \), this means the function \( f(n) \) grows slower than the threshold function \( n^{\log_b a} \), and the solution is \( T(n) = \Theta(n^{\log_b a}) \).
• **Case 2:** If \( f(n) \) is \( \Theta(n^{c}) \) where \( c = \log_b a \), the function matches the threshold exactly, leading to an extra logarithmic factor: \( T(n) = \Theta(n^{\log_b a} \log n) \).
• **Case 3:** If \( f(n) \) is \( \Omega(n^{c}) \) with \( c > \log_b a \), then \( f(n) \) dominates growth, and \( T(n) = \Theta(f(n)) \).

Understanding which case applies involves comparing the computed \( \log_b a \) term to the exponent in \( f(n) \) and using the appropriate theorem rule.
An example is recurrence (a): \( T(n) = 8T(n/2) + n \), where \( n^{\log_2 8} = n^3 \). Since \( f(n) = n \) is \( O(n^1) \) and \( 1 < 3 \), we have \( T(n) = \Theta(n^3) \) according to Case 1.

Recursion trees are a visual method used to understand how recursive functions break down problems and distribute workloads across subproblems. They are particularly useful when dealing with recurrences that may not fit the conditions for direct application of the Master Theorem. By visually displaying the recursive calls, you can track how costs multiply and sum through each level of the tree.
The basic idea is to:

• Represent the initial problem at the root.
• Each child node represents a subproblem from the parent node's problem.
• Repeat until reaching a base case, typically a known value or simple computation.

Consider recurrence (d), \( T(n) = T(n/4) + 1 \). Constructing a recursion tree involves splitting the problem into subproblems, each smaller by a factor of 4, and noting that each step contributes 1 unit of work.

• The depth of the tree, \( \log_b n = \log_4 n \) where each level sums to 1, tells us the complete height.
• The total work can then be calculated by multiplying the constant contribution by the number of levels, resulting in \( T(n) = \Theta(\log n) \).

Recursion trees help identify repeated patterns and provide insight into the relationship between recursive calls.

Big Theta notation \( \Theta \) is a way to describe the asymptotic tight bound of functions. It’s used to mathematically express that a particular function grows at the same rate as another comparable function for sufficiently large inputs. In terms of recurrence relations, it helps in understanding the efficiency and limits of algorithms.
When a function \( f(n) = \Theta(g(n)) \), this indicates that:

• There exist positive constants \( c_1 \), \( c_2 \), and \( n_0 \) such that for all \( n \geq n_0 \),
• the function \( f(n) \) is sandwiched between \( c_1g(n) \) and \( c_2g(n) \).

In simpler terms, \( f(n) \) grows neither faster nor slower asymptotically than \( g(n) \). It provides both the upper and the lower bounds compactly, offering a precise sense of efficiency unlike Big O, which only provides an upper limit.
Applying this to recurrence (b), \( T(n) = 8T(n/2) + n^3 \) uses the Master Theorem by directly comparing \( n^3 \) with the threshold \( n^{\log_2 8} = n^3 \), meaning both functions grow at the same rate. Hence, \( T(n) = \Theta(n^3 \log n) \), indicating precise bounds while capturing the logarithmic factor required in Case 2 of the theorem.