- #1
22990atinesh
- 143
- 1
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.
##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.