Master's Theorem is known to me, but I can't understand how to apply this theorem to this problem. So, how I will find Θ of T(n)?
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Define $X(n) = T (2^n)$.
Then $X(n) = T (2^n) = 3T(2^{n/2}) + n = 3X(n/2) + n$.
You solve the recurrence for $X(n)$, and $T(m) = X (\log m)$.
