title: Complexity of T(n)=16T(n/4)-2n^2
body: <p>I'm having difficulties solving this recurrence relation: T(n)=16T(n/4)-2n^2. From my understanding I can't use the master theorem because f(n) is only allowed to be positive. Because of that I tried using the recurrence method:</p>
  <pre><code>T(n) = 16T(n/4)-2n^2
  T(n) = 16(16T(n/16)-2(n/4)^2)-2n^2
  T(n) = 16(16(16T(n/64)-2(n/16)^2)-2(n/4)^2)-2n^2
  </code></pre>
  <p>So this brings me to:</p>
  <pre><code>T(n) = 16^i * T(n/4^i) - (i*2*n^2)
  
  T(n) terminates when n/4^i=1 so i = log4(n)
  </code></pre>
  <p>When I insert this into the equation I get:</p>
  <pre><code>T(n) = 16^log4(n) - (2*n^2*log4(n))
  </code></pre>
  <p>So would this bring me to a complexity of</p>
  <pre><code>T(n) = θ(n^2*log4(n)) ? 
  </code></pre>
  <p>Thanks so much!</p>