Algorithm Time and Space Complexity

Question

It is a Textbook Assignment question in my Sophomore

Tried solving it for 3 days but having a hard time.

The question is:

Find the Time and Space complexity , along with the Value Returned and No of function calls

rec(n)
{
    if( n <= 2 )
        return 1;

    return 2*rec(sqrt(n)) + 2*rec(sqrt(n)) + log(n);
}

I got TC as Θ(Logn), value returned as Θ(log^2(n)), number of function calls as Θ(LogLogn) and space complexity as Θ(LogLogn)

can anyone please help.

what is wrong and what's the right way if I am wrong!

Original problem statement @ https://ibb.co/Z8SvHcf

Chandler Bong · Answer

The recurrence relation describing the problem is:

 T(n) = 2T(√n) + logn

Now we define S(n) = T(e^n) And we get:

S(n) = T(e^n) = 2T(√(e^n)) + log(e^n) = 2T(e^(n/2)) + n = 2S(n/2) + n

After applying master theorem we get:

S(n) = Θ(nlogn)

For n > 0 we have

T(n) = S(logn) = Θ(lognloglogn)