What is the general form of a recurrence relation used in the Master Method?

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

Fill in the blank: The time complexity for the recurrence T(n) = 2T(n/2) + cn is ______.

Θ(n log n)

True or False: The recurrence relation T(n) = T(n - 1) + n has a time complexity of O(n).

False. The time complexity is O(n²).

In the Master Method, if f(n) = Θ(n^c) where c > log_b(a), then T(n) is equal to ______.

Θ(f(n))

Riddle: I can be solved using a guess and prove method, often involving induction. What am I?

Substitution Method

What is the time complexity of the Tower of Hanoi problem?

O(2^n)

Fill in the blank: The recurrence T(n) = T(√n) + 1 can be transformed using the substitution n = 2^m into ______.

T(2^m) = S(m) = S(m/2) + 1

True or False: The recurrence T(n) = 2T(n/2) + √n leads to a time complexity of Θ(n).

True.

Which of the following recurrence relations can be solved using the Master Method? A) T(n) = 2T(n/2) + n B) T(n) = T(n - 1) + n C) T(n) = T(√n) + 1 D) T(n) = 2T(n/2) + n/log(n)

A) T(n) = 2T(n/2) + n

Riddle: I am a technique that visualizes the levels of a recurrence to calculate total work done. What am I?

Recurrence Tree Method