CODEWITHSUNDEEP
recursionbig-ocomplexity-theoryrecurrence
Jay
Jay

Reputation: 357

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

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.

Upvotes: 4

Views: 37824

Answers (4)

Krish
Krish

Reputation: 1

After log(n!) We all know;
    n!=n(n-1)(n-2)....
    n!=n.n.n.n.... 
(because if we consider only highest term then it's n so...)
    n!=n^n

Now put it to our question so,
    T(n)=1+log(n!)
    T(n)=1+log(n^n)
    T(n)=1+n(log(n))   
(According log property)

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65458

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.

Upvotes: 6

templatetypedef
templatetypedef

Reputation: 372784

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!

Upvotes: 12

vonbrand
vonbrand

Reputation: 11791

Yes, this is a linear recurrence of the first order. It can be solved exactly. If your initial value is $T(1) = 0$, you do get $T(n) = \log n!$. You can approximate $\log n!$ (see Stirling's formula): $$ \ln n! = n \ln n - n + \frac{1}{2} \ln \pí n + O(\ln n) $$

[Need LaTeX here!!]

Upvotes: 0

Related Questions