title: Solving the recurrence T(n) = T(n/2) + lg n?
body: <p>I am having some issues on how to solve recurrence relations. </p>
  
  <blockquote>
    <p>T(n) = T(n/2) + log2(n), T(1) = 1, where n is a power of 2</p>
  </blockquote>
  
  <p>This is a homework problem, so don't just give me the answer. I was just wondering how to start the problem.</p>
  
  <p>In class we went over <a href="http://en.wikipedia.org/wiki/Master_theorem" rel="nofollow">the Master theorem</a>. But I don't think that would be the best way to solve this particular relation. </p>
  
  <p>I don't really know how to start the problem... should I just be going </p>
  
  <pre><code>T(n) = T(n/2) + log_base2(n)
  T(n/2) = [T(n/4)+log_base2(n/2)]
    T(n) = [T(n/4)+log_base2(n/2)] + log_base2(n) 
  </code></pre>
  
  <p>And just keep working my way down to get something I can see makes a basic equation?</p>