What's the time complexity of $T(n) =\sqrt{99nT(\sqrt {n})+100n}$?

Question

What's the time complexity of $T(n) =\sqrt{99nT(\sqrt {n})+100n}$ ,

I don't have an idea for solve the question.

My attempt :

$\frac{T(n)}{\sqrt {n}}^2 =99T(\sqrt {n})+100 $ and $\ s(k)= \frac{T(n)}{\sqrt {n}}$ but it's not useful .

Answer 1

You don't need to solve this recurrence. You should find asymptotic. Ok, let $$ T(n)\sim n^k. $$ You have: $$ T(n) = \sqrt n\sqrt{99T(\sqrt n) + 100} $$ So, $$ \sqrt n\sqrt{99T(\sqrt n) + 100}\sim \sqrt{\mathstrut n}\sqrt{99\cdot n^{k/2} + 100}. $$ If $k\ge 0$, $\sqrt{\mathstrut 99\cdot n^{k/2} + 100}\sim n^{k/4}$, and we have $$ n^k\sim n^{\frac k4 + \frac12}\Longrightarrow k = \frac k4 + \frac12 \Longrightarrow k = \frac23. $$ If $k < 0$, LHS grows like $\sqrt n$, and $k$ must be equal to $1/2$ — contradiction.

So, you have $$ T(n) = O(n^{2/3}). $$

Answer 2

Firstly, an equation does not have time complexity. What you should ask is the asymptotic complexity of $T(n)$ as $n \to \infty$, where $T$ satisfies the given equation for any natural $n$.

To get an idea of what the answer should be, iteratively bound it. You presumably are given that $T(n) \ge 0$, otherwise things won't work. $\def\nn{\mathbb{N}}$ $\def\wi{\subseteq}$

$T(n) \ge \sqrt{100n} \ge 10$ for any $n \ge 1$.

$T(n) \ge \sqrt{99nT(\sqrt{n})}$. [We take the asymptotically larger term.]

$T(n) \le \sqrt{99nT(\sqrt{n})+10T(\sqrt{n})} \le \sqrt{109nT(\sqrt{n})}$ for any $n \ge 1$.

These two bounds are close enough that we can use them to find the first-order asymptotic behaviour. You first guess it by seeing what happens if equality holds as Michael did. That guess may be false but we can see if it works as follows.

If $T(n) \in [1,100] n^\frac{2}{3}$ for any $n \in [1,k)$:

  $T(k) \in \sqrt{[99,100] k T(\sqrt{k})} \wi \sqrt{[99,100] k [1,100] k^\frac{1}{3}} \wi [1,100]k^\frac{2}{3}$.

Therefore by induction (after checking the base cases) you get that indeed $T(n) \in Θ(n^\frac{2}{3})$ as $n \to \infty$.

Note that this method works even if there are floors and ceilings in the recurrence, which always happens in analysis of actual algorithms.