Recurrence relation problems

Question

I had the following recurrence relations on a test and I got them wrong, I am not sure why.

 1. T(n) = 2T(n/4) + O(n^0.5)

Using MT: a = 2, b = 4, f(n) = n^0.5

Comparing n^(log_4(2)) to n^0.5 => n^0.5 == n^0.5

Thus, case 3: Θ(n log n)

Apparently thats wrong, don't know why.

 2. T(n) = 3T(n/4) + O(n^0.75)

Using MT: a = 3, b = 4, f(n) = n^0.75

Comparing n^(log_4(3)) to n^0.75

Thus, case 1: Θ(n^log_4(3))

 3. T(n) = T(n/2) + T(n/3) + O(n log n)

This isn't in a form that can be solved with MT and I cannot easily find a p-value without aid. Thus, I took a stab in the dark and was wrong. No clue where to begin with this one.

 4. T(n) = 2T(n/2) + n log n

Using MT: a = 2, b = 2, f(n) = n log n

Comparing n^log_2(2) to n log n => n^1 to n log n

Case 2: Θ(n log n)

Answer 1

You may have misread or omitted some details of the Master theorem. Will refer to the Wikipedia article.

---

1)

The second case states that:

Since c_crit = 0.5 and k = 0, the final complexity is:

You just missed out the exponent on the n in front.

---

2)

This is correct.

---

4)

You missed another detail here: k = 1, and there needs to be an additional factor of log n:

---

3)

This is slightly trickier. Using the Akra-Bazzi method:

To solve for the exponent p, just use Newton-Raphson on your calculator - gives p = 0.787885.... Performing the integration by parts:

Substituting in: