Quiz: Recurrence relations and master theorem

Define a recurrence relation.

A recurrence relation is an equation that expresses a term in a sequence as a function of preceding terms.

True or False: Recurrence relations can only be linear.

False. Recurrence relations can be linear or nonlinear, depending on how terms relate to one another.

What is the base case in recurrence relations?

The base case is the initial condition that stops the recursion, providing a starting value for the relation.

Fill in the blank: A second-order recurrence relation depends on ____ previous terms.

two previous terms.

Compare linear and nonlinear recurrence relations.

- Linear: Each term is a linear combination of previous terms. - Nonlinear: Terms may involve products or powers.

What is an example of a simple recurrence relation?

The Fibonacci sequence defined as: $\displaystyle F(n) = F(n-1) + F(n-2)$ with $\displaystyle F(0) = 0, F(1) = 1$.

Cause → Effect: Why do we use recurrence relations?

To model problems where the solution depends on previous solutions, enabling recursive algorithms.

What does it mean for a recurrence to be homogeneous?

A homogeneous recurrence has no constant term; all terms are derived from previous terms.

True or False: The solution to a recurrence must always be unique.

False. A recurrence might have multiple solutions depending on initial conditions.

Identify the characteristic polynomial of $\displaystyle a_n = 3a_{n-1} + 2a_{n-2}$.

The characteristic polynomial is $\displaystyle x^2 - 3x - 2 = 0$.

Describe the iterative method for solving recurrences.

The iterative method involves expanding the recurrence step-by-step until a pattern emerges.

What is a non-homogeneous recurrence relation?

A non-homogeneous recurrence includes a constant or a function of $\displaystyle n$ that is not derived from previous terms.

Fill in the blank: The Master Theorem is used to analyze the ____ of recursive algorithms.

time complexity.

What is the purpose of substitution in solving recurrences?

To replace terms in a recurrence with their corresponding values or expressions to simplify the relation.

What are the implications of the initial conditions in recurrence relations?

Initial conditions determine the specific solution to the recurrence, affecting all subsequent terms.

List two methods for solving recurrences.

- Iteration - Characteristic Equation

What does the Master Theorem solve?

It provides a method for analyzing the time complexity of divide-and-conquer algorithms described by recurrence relations.

State the form for applying the Master Theorem.

The form is: $\displaystyle T(n) = aT(n/b) + f(n)$ where $\displaystyle a \geq 1$ and $\displaystyle b > 1$.

True or False: Master Theorem can be applied to any recurrence.

False. It applies to specific forms, particularly when $\displaystyle f(n)$ is polynomially related to $\displaystyle n^{\log_b a}$.

Fill in the blank: For $\displaystyle T(n) = 2T(n/2) + n^2$, $\displaystyle a$ is ____.

2

Compare Case 1 and Case 3 of the Master Theorem.

Case 1: $\displaystyle f(n)$ is polynomially smaller than $\displaystyle n^{\log_b a}$. Case 3: $\displaystyle f(n)$ is polynomially larger.

What is the condition for Case 2?

$\displaystyle f(n)$ must be asymptotically equal to $\displaystyle n^{\log_b a}$, specifically $\displaystyle f(n) = \Theta(n^{\log_b a} \log^k n)$ for some $\displaystyle k \geq 0$.

Solve the recurrence: $\displaystyle T(n) = 3T(n/4) + n$.

Here, $\displaystyle a=3$, $\displaystyle b=4$. Calculate $\displaystyle \log_b a = \log_4 3 \approx 0.792$. $\displaystyle f(n) = n$ is polynomially smaller. So, $\displaystyle T(n) = \Theta(n^{\log_4 3})$.

What happens if $\displaystyle f(n)$ grows faster than $\displaystyle n^{\log_b a}$?

If $\displaystyle f(n)$ satisfies regularity conditions, then $\displaystyle T(n) = \Theta(f(n))$ according to Case 3 of the theorem.

True or False: $\displaystyle T(n) = T(n/2) + n^3$ is solvable by Master Theorem.

True. Here, $\displaystyle a=1$, $\displaystyle b=2$, and $\displaystyle f(n)=n^3$ is larger than $\displaystyle n^{\log_2 1}=1$. Satisfies Case 3.

What is the regularity condition?

It states that $\displaystyle af(n/b) \leq cf(n)$ for some constant $\displaystyle c < 1$ and sufficiently large $\displaystyle n$.

Identify $\displaystyle f(n)$ in $\displaystyle T(n) = 4T(n/2) + n \log n$.

$\displaystyle f(n) = n \log n$.

What is the final result for $\displaystyle T(n) = 4T(n/2) + n \log n$?

Since $\displaystyle f(n)$ is polynomially larger than $\displaystyle n^{\log_2 4}=n^2$, we apply Case 3: $\displaystyle T(n) = \Theta(n \log n)$.

Solve $\displaystyle T(n) = T(n/3) + n^2$ using Master Theorem.

$\displaystyle a=1$, $\displaystyle b=3$. Here, $\displaystyle \log_3 1 = 0$. Since $\displaystyle f(n) = n^2$ is larger, $\displaystyle T(n) = \Theta(n^2)$.

For $\displaystyle T(n) = 2T(n/2) + n^{1.5}$, what is $\displaystyle \log_b a$?

$\displaystyle \log_2 2 = 1$. Compare with $\displaystyle f(n) = n^{1.5}$.