# Can't under stand change of variable

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 ??

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}^+$]

• 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 – Xax Dec 25 '13 at 12:15
• 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. – swarnim_narayan Dec 25 '13 at 12:33