2

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 .

Amir
  • 445

2 Answers2

3

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.

user21820
  • 57,693
  • 9
  • 98
  • 256
  • @MichaelGaluza: Here is my answer. As I said, your method is the first step, and is good enough if we assume the existence of asymptotic behaviour. But a little work is needed to remove that assumption. (About my comment on limits of recursive sequences, you may be interested to look at http://math.stackexchange.com/a/624037/21820 where the convergence is a highly non-trivial issue. I don't know why my answer got downvoted, especially since the other answer is the incorrect one. If you spot any mistake in my answer please tell me. – user21820 Aug 03 '15 at 07:45
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}). $$

Michael Galuza
  • 4,730
  • what's the LHS grows? – Amir Aug 03 '15 at 06:19
  • @Amir, see my edit – Michael Galuza Aug 03 '15 at 06:21
  • Your answer is wrong because it assumes without proving that the asymptotic growth of $T$ is a power of $n$. – user21820 Aug 03 '15 at 06:21
  • @user21820, first answer: it works. Second answer: we proved it! – Michael Galuza Aug 03 '15 at 06:22
  • No. All your deductions are based on an assumption of the asymptotic growth. You didn't prove it. Getting the right answer does not mean your method is correct, just like guessing sometimes gets the answer. – user21820 Aug 03 '15 at 06:26
  • @MichaelGaluza Thx but it's a little strange for me how can improve myself to sole questions like it ? – Amir Aug 03 '15 at 06:30
  • @Amir, I can recommend to you Knuth's Concrete mathematics – Michael Galuza Aug 03 '15 at 06:33
  • @MichaelGaluza Thx a lot .It seems a good book. – Amir Aug 03 '15 at 06:40
  • And looking at your other answer you do seem to know how to use asymptotics, so I don't see why you insist you are correct here when it's obviously not the case. – user21820 Aug 03 '15 at 06:53
  • @user21820 what's your idea to solve this question ? – Amir Aug 03 '15 at 06:57
  • @user21820, may be you show us your (probably completely rigorous and brilliant) solution? Please, go ahead. – Michael Galuza Aug 03 '15 at 06:57
  • @Amir: Okay I will post an answer in a bit. It's not that Michael's answer is totally wrong, but is just the first step. The error is in assuming that $T$ has a certain asymptotic behaviour to figure out the constant. Indeed if $T(n)$ is proportional to a power of $n$ asymptotically, then Michael's answer correctly finds the power. But one still has to go through another means to prove that $T$ has the assumed asymptotic behaviour. Similarly if asked to prove the limit of some recursive sequence one can find it under assumption that it exists but still have to prove existence separately. – user21820 Aug 03 '15 at 07:14
  • @user21820 I think we can use asymptotic series for rigorous proof. Or Puiseux series. But it's long, sound and meaningless. – Michael Galuza Aug 03 '15 at 07:19
  • @MichaelGaluza: Asymptotic series is not even guaranteed! You can't assume every function has an asymptotic series... – user21820 Aug 03 '15 at 07:22