Algorithms

Question

Solve the recurrence relation

$T(n) = T(\sqrt{n}) + n$

Comments

And what the code for time complexity

int x=0;
int A(n)
{
    
    if(n==1) return 1;
    else
    {
        X+=A(root(n))+n;
    }
    return X;
}

right?

---

@gauravkc I think , the expression is not in master's applicable form. Correct if I am wrong

---

@Prashant

https://gateoverflow.in/3700/gate2004-it-57

https://gateoverflow.in/2444/gate1994-1-7-isro2017-14

See these two references

here recurrence relation arises complexity only

then how u got O(1) for complexity??