title: Solving the similar recurrence: T(n) = 3T(n/3) + n/3
body: <p>Given..</p>
  
  <pre><code>T(0) = 3 for n &lt;= 1
  
  T(n) = 3T(n/3) + n/3 for n &gt; 1
  </code></pre>
  
  <p>So the answer's suppose to be <code>O(nlogn)</code>.. Here's how I did it and it's not giving me the right answer:</p>
  
  <pre><code>T(n) = 3T(n/3) + n/3
  
  T(n/3) = 3T(n/3^2) + n/3^2
  </code></pre>
  
  <p>Subbing this into T(n) gives..</p>
  
  <pre><code>T(n) = 3(3T(n/3^2) + n/3^2) + n/3
  
  T(n/3^2) = 3(3(3T(n/3^3) + n/3^3) + n/3^2) + n/3
  </code></pre>
  
  <p>Eventually it'll look like..</p>
  
  <pre><code>T(n) = 3^k (T(n/3^k)) + cn/3^k
  </code></pre>
  
  <p>Setting <code>k = lgn..</code></p>
  
  <pre><code>T(n) = 3^lgn * (T(n/3^lgn)) + cn/3^lgn
  
  T(n) = n * T(0) + c
  
  T(n) = 3n + c
  </code></pre>
  
  <p>The answer's <code>O(n)</code> though..What is wrong with my steps?</p>