Calculating the Recurrence Relation T(n)=T(n-1)+logn
big-o, complexity-theory, recurrence, recursion
Solution
This expands out to log (n!). You can see this because
T(n) = T(n - 1) + log n
= T(n - 2) + log (n - 1) + log n
= T(n - 3) + log (n - 2) + log (n - 1) + log n
= ...
= T(0) + log 1 + log 2 + ... + log (n - 1) + log n
= T(0) + log n!
The exact answer depends on what T(0) is, but this is Θ(log n!) for any fixed constant value of T(0).
A note - using Stirling's approximation, Θ(log n!) = Θ(n log n). That might help you relate this back to existing complexity classes.
Hope this helps!
Problem
We are to solve the recurrence relation through repeating substitution: ``` T(n)=T(n-1)+logn ``` I started the substitution and got the following. ``` T(n)=T(n-2)+log(n)+log(n-1) ``` By logarithm product rule, log(mn)=logm+logn, ``` T(n)=T(n-2)+log[n*(n-1)] ``` Continuing this, I get ``` T(n)=T(n-k)+log[n*(n-1)*...*(n-k)] ``` We know that the base case is T(1), so n-1=k -> k=n+1, and substituting this in we get ``` T(n)=T(1)+log[n*(n-1)*...*1] ``` Clearly n*(n-1)*...*1 = n! so, ``` T(n)=T(1)+log(n!) ``` I do not know how to solve beyond this point. Is the answer simply O(log(n!))? 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.