title: Solving Recurrence Relation via Recursion Trees of the Form "T(n-1)"
body: <p>I understand that the Master Theorem and recursion tree can be used for "divide-and-conquer" recurrence relations (i.e. <strong>T(n)=T(n/2)+1</strong>).</p>
  
  <p>However, how would I apply those concepts to T(n)=T(n-1)+logn?</p>
  
  <p>To my understanding, you cannot apply the two concepts to (n-1) decrements. But the assignment and professor are requiring T(n)=T(n-1)+logn to be solved using recursion trees and master theorem.</p>
  
  <p>Furthermore, is there any reason that the following is not the recursive expansion for the above function?</p>
  
  <pre><code>T(n)=T(n-3)+log(n-2)+log(n-1)+log(n)
  </code></pre>
  
  <p>According to my professor, it should not be log(n-2) and log(n-1) but rather </p>
  
  <pre><code>T(n)=T(n-3)+logn+logn+logn
  </code></pre>
  
  <p>which makes absolutely no sense to me.</p>