Recurrence Relations and Master Theorem Quiz

What is a recurrence relation in the context of algorithm analysis?

• A loop-based computation formula

• An equation that describes a function in terms of its value on smaller inputs

• A statistical method to forecast future values

• A function that always returns constant time

Which of the following is a divide-and-conquer recurrence form?

• T(n) = T(n-1) + 1

• T(n) = n + 1

• T(n) = aT(n/b) + f(n)

• T(n) = T(n-2) + T(n-1)

What is the first step in solving a recurrence using the substitution method?

• Apply the Master Theorem

• Guess the form of the solution

• Draw the recursion tree

• Solve the base case

In solving T(n) = 2T(n/2) + n by substitution, what is a reasonable guess for the solution?

• O(n)

• O(n^2)

• O(n log n)

• O(log n)

What does the recursion tree method primarily help you identify?

• The exact runtime of any algorithm

• The flowchart of an algorithm

• The cost at each level and total cost across recursive levels

• The loop structure in recursive calls

For the recurrence T(n) = 2T(n/2) + n, what is the cost at each level of the recursion tree?

• Halved each level

• Constant at each level

• Increases exponentially

• Remains n at each level

In the Master Theorem, what does the function f(n) represent?

• The number of recursive calls

• The input size

• The cost of dividing and combining work

• The base case value

Which case of the Master Theorem applies when f(n) = O(n^log_b a)?

• Case 1

• Case 2

• Case 3

• None of the above

For T(n) = 2T(n/2) + n, which case of the Master Theorem applies?

• Case 1

• Case 2

• Case 3

• Cannot be solved using Master Theorem

What is the solution to T(n) = 4T(n/2) + n^2 using the Master Theorem?

• O(n^2)

• O(n^2 log n)

• O(n log n)

• O(n^3)