Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Solving recurrence by changing variables

  1. Dec 22, 2015 #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.
     
  2. jcsd
  3. Dec 23, 2015 #2

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    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##.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook