# Solving recurrence by changing variables

Tags:
1. Dec 22, 2015

### 22990atinesh

Consider the below recurrence
$T(n) = 2 T(\sqrt(n)) + \log n$
substituting $\log n = m \implies n = 2^m$
$T(2^m) = 2 T(2^{\frac{m}{2}}) + m$
substituting $S(k) = T(2^m)$ I'm getting below equation
$S(k) = 2 S(\frac{k}{2}) + m$
How can I change 'm' to 'k' in above equation.

2. Dec 23, 2015

### Samy_A

You need to define the relation between $k$ and $m$ when setting $S(k) = T(2^m)$.
You could define $S$ by $S(m)=T(2^m)$.
Then you get $S(m)=2S(\frac{m}{2}) + m$.