Recurrence relation problems
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)
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:
