I am confused about example we got today in class. Here is a recurrence and I am not sure how we got
$S(m)=S(m/2)+(\lg m)$
$$T(n)=T(\sqrt{n}) + (\lg\lg n) $$ Let $$m =\lg n$$ $$S(m)=S(m/2)+(\lg m) $$
Case2 of MT $$ ((\lg\lg n)^2)$$
How did we get m/2 ?
$2^m = n$ and $\sqrt{2^m} = 2^{m/2}$ not $m/2$
Also why is it Case 2?