Calculating the Recurrence Relation T(n)=T(n-1)+logn

Question

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.

Answer 1

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!

Answer 2

Stirling's formula is not needed to get the big-Theta bound. It's O(n log n) because it's a sum of at most n terms each at most log n. It's Omega(n log n) because it's a sum of at least n/2 terms each at least log (n/2) = log n - 1.