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##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Solving recurrence by changing variables
  1. Static Variables (Replies: 5)

  2. Global variables. (Replies: 7)

Loading...