title: Complexity of T(n) = 2T(n/2) + n/2 (without master's theorem)?
body: <p>I am looking at the best case running time for merge sort, and have found the following recurrence relation: T(n) = 2T(n/2) + n/2. I am aware of the fact that merge sort is theta(nlogn) in all cases. In attempting to solve this recurrence relation, I use telescoping:</p>
  <pre><code>T(n) = 2*T(n/2) + n/2
  T(n) = 2^2*T(n/4) + n/4 + n/2
  T(n) = 2^k*T(1) + (n/2 + n/4 + ... + n/2^k) 
  2^k = n -&gt; log_2(n) = k
  T(n) = n + n(1/2 + 1/4 + ... + 1/n) 
  </code></pre>
  <p>I am unsure how to solve the summation in the last part... I'm not even sure if that is correct. My thinking is that there would be log_2(n) total items being added in the summation? I am unsure how to derive that 2T(n/2) + n/2 is theta(nlogn) <strong>without using the master's theorem please</strong>...</p>