Master Theorem. Use the master theorem to solve the following recurrences. Justi

Question

Master Theorem. Use the master theorem to solve the following recurrences. Justify your results (i.e. state what case you use and why you use this case). Assume T(1) = 1. T(n) = 2T(n/2) + n^2 T(n) = 64T(n/4) + Squareroot n. T(n) = 9T(n/3) + n^2 log n. T(n) = 32T(n/2) + n^2 log n. Strassen's Algorithm. Apply Strassen's algorithm to compute: (1 1 1 1 2 1 2 1 1 2 1 2 2 2 2 2) middot (1 1 1 1 2 1 2 1 1 2 1 2 2 2 2 2) The recursion should exit with base case n = 1, so 2 times 2 matrices should be recursively computed.

Explanation / Answer

There are following three cases:

1. If f(n) = (nc) where c < Logba then T(n) = (nLogba)

2. If f(n) = (nc) where c = Logba then T(n) = (ncLog n)

3.If f(n) = (nc) where c > Logba then T(n) = (f(n))

(a) T(n) = 2T(n/2) + n2

here f(n) = n2 i.e. c = 2 > log22 =1 , hence T(n) = (n2) ... [ case 3]

(b) T(n) = 64T(n/4) + root(n)

here f(n) = n1/2 i.e. c= 1/2 < log464 = 3 , hence T(n) = (nLogba) = (n3) ...[ case 1]

(c) T(n) = 9T(n/3) + n2log n

Note : Case 2 can be extended for f(n) = (ncLogkn)
If f(n) = (ncLogkn) for some constant k >= 0 and c = Logba, then T(n) = (ncLogk+1n)

here, c = 2, k= 1 & logba = log39 = 2 = c . hence, T(n) = (n2log2n)

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---