Solve the recurrence: $T(n) = \sqrt{2n}T(\sqrt{2n})+\sqrt{n}$

Question

I found a recurrence of a similar form on this forum, but I couldn't use it to gain any intuition for my question. So far, I've tried 3 things. I've tried unrolling it but could not really see a pattern. I've tried transforming it in hopes that I would be able to use Master's Theorem, but no such luck. I've also tried to guess a complexity and apply induction to see if I can simplify it but I haven't been able to reach a tight bound.

EDIT: Assume that $T(n)$ is constant for $n \leqslant 3$

Answer 1

Use the variable change:

$\begin{align*} n &= 2 \cdot 2^{2^k} \\ k &= \log_2 \left(\log_2 \frac{n}{2}\right) \\ \sqrt{2 n} &= \sqrt{2 \cdot 2 \cdot 2^{2^k}} \\ &= 2 \cdot 2^{2^{k - 1}} \\ \sqrt{n} &= \sqrt{2} \cdot 2^{2^{k - 1}} \\ t(k) &= T(2 \cdot 2^{2^k}) \end{align*}$

We get the nice (?) recurrence:

$\begin{align*} t(k) &= 2 \cdot 2^{2^{k - 1}} t(k - 1) + \sqrt{2} \cdot 2^{k - 1} \\ \end{align*}$

(it is nice in that it is a linear recurrence of first order thus solvable).

Divide through by $2^k \cdot 2^{2^k}$, simplify,

$\begin{align*} \frac{t(k)}{2^k \cdot 2^{2^k}} - \frac{t(k - 1)}{2^{k - 1} \cdot 2^{2^{k - 1}}} &= \frac{\sqrt{2}}{2^k \cdot 2^{2^{k - 1}}} \end{align*}$

Sum over $1 \le k \le r$, the left hand side telescopes nicely:

$\begin{align*} \frac{t(r)}{2^r \cdot 2^{2^r}} - \frac{t(0)}{2^0 \cdot 2^{2^0}} &= \sum_{1 \le k \le r} \frac{\sqrt{2}}{2^k \cdot 2^{2^{k - 1}}} \\ t(r) &= 2^{r - 1} \cdot 2^{2^r} t(0) + \sqrt{2} \cdot 2^r \cdot 2^{2^r} \cdot \sum_{1 \le k \le r} 2^{-k} \cdot 2^{-2^{k - 1}} \end{align*}$

We get a (very crude) upper bound on the sum by:

$\begin{align*} \sum_{1 \le k \le r} 2^{-k} \cdot 2^{-2^{k - 1}} &\le \sum_{1 \le k \le r} 2^{-k} \\ &< \sum_{k \ge 1} 2^{-k} \\ &= \frac{1}{2} \end{align*}$

This gives the bound:

$\begin{align*} t(r) &\le 2^{r - 1} \cdot 2^{2^r} t(0) + \sqrt{2} \cdot 2^{r - 1} \cdot 2^{2^r} \end{align*}$

A matching lower bound is given by the sum being larger than 0.

This means (throw in a constant to simplify):

$\begin{align*} t(r) &= \Theta\left(2^r \cdot 2 \cdot 2^{2^r}\right) \\ T(n) &= \Theta\left(2^{\log_2 \log_2 n} \cdot n\right) \\ &= \Theta(n \log n) \end{align*}$

Phew!

Answer 2

Let $n\mapsto2n$, divide both sides by $n$, and $f(n)=T(2n)/n$ to get

$$f(n)=2f(\sqrt n)+\sqrt{\frac2n}$$

Now let $n\mapsto2^n$ and $g(n)=f(2^n)$ to get

$$g(n)=2g(n/2)+\sqrt2\cdot2^{n/2}$$

to which you may apply Master's theorem and work backwards.

Answer 3

Making $m=2n$ we have

$$ T(2m)=2\sqrt{m}T(2\sqrt{m})+\sqrt{2m} $$

and now making $\mathcal{T}(\cdot) = T(2(\cdot))$ we have

$$ \mathcal{T}(m) = 2\sqrt{m}\mathcal{T}(\sqrt{m})+\sqrt{2m} $$

and

$$ \mathcal{T}\left(2^{\log_2 m}\right) = 2\sqrt{m}\mathcal{T}\left(2^{\log_2 \sqrt{m}}\right)+\sqrt{2m} $$

Considering now

$$ \mathbb{T}(\cdot) = \mathcal{T}\left(2^{(\cdot)}\right),\ \ \ z = \log_2 m $$

we follow with the recurrence

$$ \mathbb{T}(z) = 2\times 2^{\frac z2}\mathbb{T}\left(\frac z2\right)+2^{\frac{z+1}{2}} \ \ \ \ \ \ \ (1) $$

with solution

$$ \mathbb{T}(z) = z 2^{z+\frac 12}\left(C_0-\sum_{k=0}^{\log_2 z-1}2^{-2^{k-1}+k}\right) $$

and now backwards, we can obtain $T(n)$

NOTE

Regarding the recurrence $(1)$ we can follow with the transformation

$$ F(\cdot) = \mathbb{T}\left(2^{(\cdot)}\right),\ \ \ u = \log_2 z $$

reducing it to

$$ F(u) = 2\times 2^{\frac {2^u}{2}}F(u-1)+2^{\frac{2^u+1}{2}} $$

This recurrence easily gives the result for $(1)$