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

CodePudding user response：

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)

You will find a more in-depth discussion here: https://cs.stackexchange.com/questions/96422/how-to-solve-tn-2t√nlog-n-with-the-master-theorem?newreg=0deef64b56714962a0cd046f7f0ca745 Hope this helps.