Question

(1) T(n)=9⋅T(n3)+n2⋅(log⁡(n))2

(2) T(n) = 10 * T(n/3) + n^2

One of these can be solved using the Master Theorem; the other cannot.

1. Which one can be solved using the Master Theorem? Compute the solution to this recurrence relation.
2. Which one cannot be solved using the Master Theorem? Carefully explain why not.
   (NOTE: A complete solution will use the definition of big-O.)
3. Use another method to solve this recurrence relation. To make this a bit easier, you may assume that n = 3^k for some integer k (so that k = log₃(n)).
   {NOTE: If you use a recursion tree, you clearly cannot sketch it here. You can (and should) indicate the number of nodes -- for recursive calls -- at each level, the time complexity of each node, and the total time complexity for each level.)

Answer 1

Ans: First one can't be solved using master thorem

Because for master thorem it should be of form:

T(n) = aT(n/b) + f(n)

1) T(n) = 9.T(n^3) + f(n)

Here inside T(n^3) this term is not allowed according to master thorem form n should linear

2) T(n) = 10* T(n/3) + n^2

This can be solved because this is of master thorem form:

Sol: calculate n to the power log a base b;

Power(n , log 10 base 3) =n^ 2.095

F(n) = n^2;

So power(n, log 10 base 3) > F(n)

Complexity is theta(n^2.093)

n= 3^ k for solving second one

After substituting it :

T(3^k) = T(3^k-1) + (3^k)^2

T(3^k) = S(m)

S(m) = S(m-1) + m^2

Sol: using substitution: s(m) = S(m-2) + (m-1)^2 + m^2

S(m) = s(m-3) +( m-2)^2 +(m-1)^2+ m^2

...

..

Upto m times

S(m) = S(0) + 1^2 + 2^2 + 3^2 .... + m^2

Sum of n squared terms: n(n+1)(2n+1)/6

S(m) = S(0) + m(m+1)(2m+1)/6

S(m) = O(m^3)

K= log n base 3

M= 3^k = n

T(n) = O(n^3)

I hope this solution helps you give an upvote!!