title: solving T(n) = 2T(n/2) + log n
body: <p>I am trying to solve T(n) = 2T(n/2) + log n</p>
  
  <p>substituted n = 2^k</p>
  
  <pre><code>T(2^k) = 2T(2^(k-1)) + k  
  T(2^k) = 2^2 T(2^(k-1)) + 2(k-1) + k
  
  after k steps
  T(2^k) = 2^k T(1) + 2^(k-1) + 2 * (2^(k-2)) +....+k
  </code></pre>
  
  <p>So basically I need to sum a term of i*2^i where i = 1 to log n - 1.<br>
  And I could not find an easy way to sum these terms. Am I doing something wrong ? Is there any other way to solve this recursion ? would master theorem work her ? if yes than how ?</p>
  
  <p>Thanks.</p>