3

How to solve the recurrence relation:

$\displaystyle T(n) = \begin{cases} \sqrt{2T\left(\frac n2\right)} + \log_2(n) & \mbox{if }\ n>2\\ 1 & \mbox{if }\ n\leq2 \end{cases}$

n is set of all real numbers

I am not sure how to remove the sqrt, by some substitution. i tried multiple methods by replacing with a different function but i was unable to remove it.

Did
  • 279,727
Llm Linux
  • 31

1 Answers1

2

Judging by the name of your function and the base $2$ logarithm, this recurrence arises from estimating the running time of an algorithm, in which case we only care about the value of $T(n)$ up to a multiplicative factor as $n\to\infty$. We may apply a variant of the master theorem to resolve such questions.

In this case, it is convenient to change variables by setting $a_k=T(2^k)$ so that $a_{k}=\sqrt{2a_{k-1}}+k$. Clearly $a_k>k$, and a simple induction shows that $a_k<2k$ as well. Therefore $T(n)$ grows logarithmically. (In fact, with more work we can get that $T(n)=(1+o(1))\log_2(n)$.

pre-kidney
  • 30,223
  • Yes i am trying to find the running true, as i was unable to solve with Masters theorem, i thought of solving the recurrence.

    Master theorem can be applied of the form

    $T(n) = aT(n/b) + f(n)$

    here There is $sqrt{T(n/2)}$ so i am not sure if i can apply masters theorem, can you please explain ?

     – Llm Linux Jul 31 '16 at 10:50
  • A bit late to the party, but I disagree with your assessment that because it is estimating the running time of an algorithm we only care about asymptotic behavior. Constants matter a lot in the real world. I don't understand the general disconnect from reality in academia and the absolute obsession with asymptotics. – orlp Jul 03 '19 at 10:45
  • @orlp, asymptotic behavior can include constants - as you can see from my parenthetical remark at the end of the post. In fact, I would argue that the point of studying asymptotics of a function is rooted in practical reasoning: more practical in many cases than deriving exact formulas. For instance, an asymptotic that tells you $f(n)=n^2+2+o(1/n)$ becomes more accurate the larger $n$ gets. In general one should obtain better and better asymptotics, stopping at the level of accuracy needed. Since this question had very little context, I chose to stop at the first level of accuracy. – pre-kidney Jul 04 '19 at 19:49