0
$\begingroup$

T (n) = T(√n) + 1 The easy way to do this is with a change of variables. Let m = lg n and S(m) = T (2^m).

T(2^m) = T (2^(m/2)) + 1

S(m) = S(m/2) + 1

Can any one explain why 1 and 2 are same and this works ??

$\endgroup$
3
$\begingroup$

Perhaps the concept will clear up if you try to solve the recurrence:

$T(n)=T(\sqrt{n})+1$.

Let $n\gt0$ which implies $\log_2n$ exists.

Let $m=\log_2n$ which implies $2^m=n$.

By the above statement and the first statement it is true that: $T(2^m)=T(2^{m/2})+1$. This is statement $A$

Define a new function $S$, such that $T(2^{\log_2n})=S(\log_2n)$.

$\implies T(2^m)=S(m)$ [By definition of $m$]

$\implies T(2^{m/2})=S(m/2)$.

By statement $A$ and above,

$S(m)=S(m/2)+1$.

Note that $m=\log_2 n$ and now we let $m$ be a perfect power of 2. Let $m=2^k$ where $k\ge0$. Also note that by imposing this restriction, we have also made $n=2^{2^{k}}$ thus $n$ is two raised a perfect power of 2.

Expanding the recurrence,

$S(m)=S(m/2)+1\implies S(m)=S(m/4)+2 \implies ....\implies S(m)=S(m/2^k)+k\implies S(m)=S(1)+k \implies S(m)=S(1)+\log_2 m.$

Now as $S(m)=T(n)$ [By definition of $S$ and $m$], we can write the last statement of the previous as follows:

$T(n)=\log_2\log_2 n+S(1)$

Again by definition of $S$, we get $S(1)=T(2)$ [Remember $S$ is a function in $m$ and $T$ is a function in $n$, but $m$ and $n$ are not independent. Infact $m$ has been defined as $\log_2 n$].

Hence we have a solution to your original recurrence,

$T(n)=\log_2\log_2 n + T(2).$

[Note that during the proof, we had restricted the values which $n$ could take up, but putting the solution back into the recurrence tells us that this solution works even when $dom(T)=\mathbb{R}^+$]

$\endgroup$
  • $\begingroup$ thanks,can you tell me how to find a function is asymptotically larger but not polynomial larger. like for the case t(n)=2 t(n/2)+nlogn $\endgroup$ – Xax Dec 25 '13 at 12:15
  • 1
    $\begingroup$ Thats a different question. As per site policy, you should ask this question separately along with a description of your prior attempts to solve it. $\endgroup$ – swarnim_narayan Dec 25 '13 at 12:33

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.