Master of Complexity$]$: The Master Theorem might seem easy to work with, but in some cases,

it may not apply directly. However, a good computer scientist can often find a creative way to make

it work. Consider the following recursive relation:

T $($n$)=3$T $($n$/2)+$ n$2$n log log n

$($a$)[5$ points$]$ Can the Master Theorem be applied directly to find the solution of the recursion?

Justify your answer.

$($b$)[5$ points$]$ We can express the recursion as T $($n$)=3$T $($n$/2)+($n$).$ What is the largest value

of $?$ Justify your answer and use the master theorem to solve this recursion.

$($c$)[5$ points$]$ We can also rewrite the recursion as T $($n$)=3$T $($n$/2)+$ O$($n $).$ What are the possible

choices for $?$ Justify your answer and use the master theorem to solve this recursion.

$($d$)[5$ points$]$ Find a function f $($n$)$ such that T $($n$)=$ $($f $($n$))$ is the solution of the recursion