title: Q: Solving the following recurrence: T(n) = 8T(n/8) + n log n
body: <p>I am trying to solve the following recurrence: </p>
  
  <pre><code>T(n) = 8T(n/8) + n* log n. 
  </code></pre>
  
  <p>I currently have done the following but am not sure if I am on the right track:</p>
  
  <pre><code>1. T(n)= 8 T(n/8) + n log n;
  2. T(n)= 8^2 T(n/8^2) + n log (n/8) + n log n
  3. T(n)= 8^3 T(n/8^3) + n log (n/8^2) + n log (n/8) + n log n
  </code></pre>
  
  <p>So the general formula came up for me as:</p>
  
  <pre><code>T(n)= 8^k T(n/8^k) + n log(n* n/8 * n/8^2 * ... * n/8^k).
  </code></pre>
  
  <p>And i am not sure how to continue this. I tried to rewrite the <code>log</code> as
  <code>n^k / 8^(k*(k+1)/2)</code>, but I still don't see the solution.</p>