# Solving recurrence relation $T(n) = \sqrt{(n * T(\sqrt{n}) + n)}$

I found a solution to the recurrence relation that I would like to discuss with you please:

$$T(n) = \sqrt{(n * T(\sqrt{n}) + n)} \tag{1}\label{1}$$

As I understood, a lot of recurrence relations could be solved by mapping them to the master equation and then check to which case it belongs, which is much faster than unrolling recurrence equations to find the solution for it:

$$T(n) = aT(\frac{n}{b}) + f(n)$$

Some equations though like the above \ref{1} can not be mapped directly to master method to solve it, so some transformations are necessary as follows:

\begin{align} T(n) =\sqrt{(n * T(\sqrt{n}) + n)}\\ \log{T(n)} = \frac{1}{2}\log{n\times\left(T(\sqrt{n}) + 1\right)} \tag{2}\label{2}\\ \log{T(n)} \approx \frac{1}{2}\log{n\times\left(T(\sqrt{n})\right)} \tag{3}\label{3}\\ \end{align}

First transformation: we can do our first transformation as follows by letting $$S(n)=\log{T(n)}$$

\begin{align} S(n) = \frac{1}{2}\log\left({n\times\left(T(\sqrt{n})\right)}\right) \tag{4}\label{4}\\ = \frac{1}{2}\log{n} + \frac{1}{2}\log{\left(T(\sqrt{n})\right)}\\ = \frac{1}{2}\log{n} + \frac{1}{2}S(\sqrt{n})\tag{5}\label{5}\\ \end{align}

Second transformation: Again, the input form of $$\sqrt{n}$$ could be further simplified by letting $$R(n) = S(2^n)$$, so we have:

\begin{align} S(n) = \frac{1}{2}\log{2^n} + \frac{1}{2}S(\sqrt{2^n}) \tag{6}\label{6}\\ = \frac{1}{2}n + \frac{1}{2}S(\sqrt{2^n})\\ = \frac{1}{2}n + \frac{1}{2}R(n/2) \tag{7}\label{7}\\ \end{align}

Problem 1: This is just a discussion please, so no solution is needed. In equation \ref{6}, what we are doing here is to let $$R(n)$$ takes part of the domain of the original input defined as in $$S(n)$$, so that means as I understand it that we are not taking the whole input but a form/part of it, so how that would mean that our new form/transformation defined by $$R(n)$$ is a valid please since it does not cover all the domain of $$S(n)$$ but part of it?

Problem 2: For equation \ref{7} please, how $$\frac{1}{2}S(\sqrt{2^n})$$ becomes $$\frac{1}{2}R(n/2)$$ as I guess it should be $$\frac{1}{2}R(\sqrt{n})$$, what do you think please.

Problem 3: once we get the simplified form: $$R(n)= (1/2) R(n / 2) + (1/2) n$$, if we try to apply master method here, we see that $$f(n) = (1/2)n$$ and $$c=1$$. For $$\log_b{a} = \log_2{1/2}=-1$$. We can see that $$c=1 \gt -1$$, so we have case 3 that $$c \gt \log_b{a}$$, so we have $$O(n^c) = O(n)$$, but the question I got says it's $$O(n^{\frac{2}{3}})$$, what do you think please?

Assuming that

$$\log_2{T(n)} \approx \frac{1}{2}\log_2n+\frac 12\log_2T(\sqrt{n})$$

making $$\mathcal{T}(\cdot)=\log_2T\left(2^{(\cdot)}\right)$$ and $$z = \log_2 n$$ we follow with the recurrence

$$\mathcal{T}(z)=\frac z2+\frac 12\mathcal{T}\left(\frac z2\right)$$

This recurrence has the solution

$$\mathcal{T}(z)=\frac 2z\left(\frac{4^{\log_2 z-1}}{3}+c_0\right)$$

now going backwards with $$z=\log_2 n$$ we get finally

$$T(n) = c_12^{\frac{1}{3} 2^{1-n} \left(4^n-1\right)}$$

EDIT

The required solution follows

$$\mathcal{T}(z)=\frac z2+\frac 12\mathcal{T}\left(\frac z2\right)$$

or

$$\mathcal{T}(2^{\log_2 z})=\frac z2+\frac 12\mathcal{T}\left(2^{\log_2{\frac z2}}\right)$$

now calling $$\mathbb{T}(\cdot)=\mathcal{T}\left(2^{\log_2{(\cdot)}}\right)$$ and $$u=\log_2 z$$ we follow with

$$\mathbb{T}(u)=2^{u-1}+\frac 12 \mathbb{T}(u-1)$$

This linear recurrence has the solution

$$\mathbb{T}(u)=c_0 2^{1-u}+\frac{1}{3} 2^{1-u} \left(4^u-1\right)$$

now going backwards with $$u=\log_2 z$$ we get

$$\mathcal{T}(z)=\frac 2z\left(\frac{4^{\log_2 z-1}}{3}+c_0\right)$$

• Thank you very much. One question please, we have no $2^{(.)}$ inside, so how you managed to get $z$ instead inside $\mathcal{T}(z)$? If we are to replace $n$ inside $T$ by $z$, then $z= log n$, so $2^z = n$ as I understand it. Then we will have based on how I understand $z$ the following: $\mathcal{T}(2^z) = 1/2(z) + 1/2(\mathcal{T}(2^{z/2}))$. Please correct me where I am doing wrong?
– Avv
Commented Sep 24, 2021 at 20:24
• The relationship you found is really $\log_2(T(2^z))=\frac 12 z + \frac 12 \log_2(T(2^{\frac z2}))$. The transformation gives us the $\mathcal{T}$ recurrence Commented Sep 24, 2021 at 22:44
• I applied master method and I got case 3 on$\mathcal{T}(z)=\frac z2+\frac 12\mathcal{T}\left(\frac z2\right)$. What do you think please? Since $c>log_b(a)$ so we have $O(n)$ without going for $T(n)$ back again as I understand that $\mathcal{T}$ complexity is same as of $T(n)$, is that correct please? Otherwise, how you get the solution for the recurrence equation please? Then, can you add to your solution please how you went back to $T(n)$ after you substitute the value of $z$?
– Avv
Commented Sep 24, 2021 at 23:00
• Included the solution required. Commented Sep 25, 2021 at 6:43
• Any comment con problem 1 of the OP? Commented Sep 25, 2021 at 7:11