Question

- Approach and show your work in exactly the same way as demonstrated in the example below -   

Use the Master Theorem to characterize and solve the following recurrence equations by stating at the end which case was used and why:

1. T(n) = 25T(n/5) + n

2. T(n) = 36T(n/6) + (n log n)²

3. T(n) = 8T(n/3) + n²

Theorem

       T(n) = c                          if n = 1

       T(n) = a T(n/b) + f(n)     if n > 1

Let f(n) be as above, where f(n) ∈ Θ(n^k), k >= 0

• Case 1: If a > b^k           then       T(n) = Θ(n ^log _b ^a)
• Case 2: If a = b^k           then        T(n) = Θ (n^log _b ^a log^k+1 n )
• Case 3: If a < b^k           then        T(n) = Θ(f(n) )

Case 1 Example:

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

In this case, what is f(n)?
And what are the values for a, b, and k? (a =? b =? k =?)

f(n) = 1 (Because in terms of n, 1 = n⁰)

a = 2, b = 2, k = 0

Which of the cases applies?

a = 2, and b^k = 2⁰= 1

Since 2 > 1, a > b^k=> case 1

Therefore, T(n) is Θ (n ^log ₂ ²) by the master theorem.

And since log ₂ 2= 1, that means T(n) є Θ(n).

Answer 1

1. T(n) = 25T(n/5) + n

f(n) = n

a=25 , b=5 , k=1

25 > 5¹ so  a > b^k [case 1 applies]

T(n) = Θ(n ^log_b^a) = Θ(n^log5²⁵) = Θ(n²)

============================================================================================

2. T(n) = 36T(n/6) + (n log n)²

f(n) = (n log n)²

a=36 , b=6 , k=2

36 == 6² so  a == b^k [case 2 applies]

T(n) =T(n) = Θ (n^log_b^a log^k+1 n ) = Θ(n^log6³⁶ log³n) = Θ(n² log³n)

============================================================================================

3. T(n) = 8T(n/3) + n²

f(n) = n²

a=8 , b=3 , k=2

8 < 3² so  a < b^k [case 3 applies]

T(n) = Θ(f(n)) = Θ(n²)

^{============================================================================================}