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

discrete mathematicselementary-number-theoryrecurrence-relations

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?

Best Answer

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) $$