title: Calculating the Recurrence Relation T(n)=T(n-1)+logn
body: <p>We are to solve the recurrence relation through repeating substitution:</p>
  
  <pre><code>T(n)=T(n-1)+logn
  </code></pre>
  
  <p>I started the substitution and got the following.</p>
  
  <pre><code>T(n)=T(n-2)+log(n)+log(n-1)
  </code></pre>
  
  <p>By logarithm product rule, log(mn)=logm+logn,</p>
  
  <pre><code>T(n)=T(n-2)+log[n*(n-1)]
  </code></pre>
  
  <p>Continuing this, I get</p>
  
  <pre><code>T(n)=T(n-k)+log[n*(n-1)*...*(n-k)]
  </code></pre>
  
  <p>We know that the base case is T(1), so n-1=k -> k=n+1, and substituting this in we get</p>
  
  <pre><code>T(n)=T(1)+log[n*(n-1)*...*1]
  </code></pre>
  
  <p>Clearly n*(n-1)*...*1 = n! so,</p>
  
  <pre><code>T(n)=T(1)+log(n!)
  </code></pre>
  
  <p>I do not know how to solve beyond this point. Is the answer simply <strong>O(log(n!))</strong>? I have read other explanations saying that it is Θ(nlogn) and thus it follows that O(nlogn) and Ω(nlogn) are the upper and lower bounds respectively.</p>