0
$\begingroup$

$T(n)=\sqrt{2T(n-1)}$ what will be the time complexity if $T(n)$ is given as this? I tried substitution but no result was reached.

$\endgroup$
  • 1
    $\begingroup$ Note that this isn't a question about time complexity: it's a question about solving recurrence relations. Perhaps the function $T$ does denote the running time of some algorithm, but that doesn't actually matter, for your question. $\endgroup$ – David Richerby Mar 2 '18 at 19:25
  • 2
    $\begingroup$ Possible duplicate of Solving or approximating recurrence relations for sequences of numbers $\endgroup$ – David Richerby Mar 2 '18 at 19:25
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Apr 2 '18 at 8:43
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Apr 2 '18 at 8:44
  • 1
    $\begingroup$ You are asking to solve a recurrence; it has nothing to do with "time complexity" beyond maybe where the recurrence came from. $\endgroup$ – Raphael Apr 2 '18 at 8:44
1
$\begingroup$

The answer depends on the initial value. For example, if $T(0) = 2$ then you can prove by induction that $T(n) = 2$ for all $n$. More generally, let $S(n) = T(n)/2$. Then $$ S(n) = \frac{T(n)}{2} = \frac{\sqrt{2T(n-1)}}{2} = \sqrt{\frac{T(n-1)}{2}} = \sqrt{S(n-1)}. $$ Simple induction now shows that $S(n) = \sqrt[2^n]{S(0)}$, and so $$ T(n) = 2 \sqrt[2^n]{\frac{T(0)}{2}}. $$ In particular, this shows that $T(n) \to 2$.

We can estimate the speed of convergence using the estimate $$ \sqrt[2^n]{x} = \exp \frac{\log x}{2^n} = 1 + O\left(\frac{\log x}{2^n}\right). $$ This shows that $$ T(n) = 2 + O(2^{-n}). $$

$\endgroup$
0
$\begingroup$

With substitution, we will get $T(n) = \sqrt{2\sqrt{2\sqrt{\cdots\sqrt{2}}}}$ with length $n$. Now, suppose $n$ goes to $\infty $, we will have $A = \sqrt{2A}$. Therefore, $A^2-2A = 0$ and $A = 2$. Hence, $T(n)$ would be constant as $T(n)$ is increasing. And we can write $T(n) =\Theta(1)$.

$\endgroup$
  • 1
    $\begingroup$ While I agree with your final answer, it seems like there is a gap in the justification here. It appears that you are implicitly assuming that there exists a constant $c$ such that $T(n) \to c$ as $n \to \infty$. Of course, if that is true then $T(n) = \Theta(1)$. However, while that assumption is in fact true, you never provided any evidence for that assumption. How do you know that there isn't some possible value for $T(0)$ that makes this sequence increasing, or eventually increasing? I think we need to prove that $T(n+1) < T(n)$ if $T(n)>2$, or something like that. $\endgroup$ – D.W. Mar 2 '18 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.