Can somebody look over my proof? (Asymptotic notation and algorithms)

  • #1
Hey. I'm self studying my way through an algorithms book, and one of the questions at the end of a section is to prove that [itex] log(n!) \in \Theta (n log(n))[/itex]. I wrote up what I believe is a valid proof. However, I don't have much experience writing formal proofs (and even less experience with having my proofs corrected by professionals), so it could very well be invalid/lingered with errors. Can somebody take a quick look at it and comment on any mistakes that may exist? Can you comment on my style? Any advice would be appreciated.

Here is my write-up. I apologize for not using the built-in equation editor.

http://i.imgur.com/iyAto.png
 

Answers and Replies

  • #2
296
0
I think Stirling's formula is unnecessary here. An asymptotic expression for [itex]\log(n!)[/itex] can be obtained as follows:
[tex]\log(n!)=\sum_{k=1}^{n}\log(k) \sim \int_{1}^{n}\log(x)dx[/tex]
The integral on the right side can be evaluated using integration by parts:
[tex]\int \log(x)dx = x\log(x) - \int dx = x\log(x)-x+C[/tex]
and this yields
[tex]\log(n!) \sim n\log(n)-n \sim n\log(n)[/tex]
Can you take it from there?
 
  • #3
That wouldn't be rigorous, would it? In my proof, I kept the error terms and treated them rigorously.

EDIT: The point of the problem is to proof the asymptotic behavior of the function, so it would be self defeating to use its asymptotic form. Please correct me if I am wrong, though.
 
Last edited:
  • #4
AlephZero
Science Advisor
Homework Helper
6,994
292
You can get the error bounds from post #2.
$$\log(n!) = \sum_{k=2}^n \log k$$
I changed the lower limit since ##\log 1 = 0##.

Because ##\log## is a monotonic function you can bracket the sum by two integrals
$$\int_2^n \log (x-1)\,dx < \sum_{k=2}^n \log k < \int_2^n \log x\,dx$$

Draw a picture of the integrals and the sum as a set of rectangles, if you can't see where that came from.
 
  • #5
I see! That definitely looks like a valid proof, too. The book that I'm using mentioned bounding functions using integrals, but for some reason told me to use Sterling's formula to prove the theorem.
 

Related Threads on Can somebody look over my proof? (Asymptotic notation and algorithms)

Replies
0
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
9
Views
2K
Replies
1
Views
1K
  • Last Post
Replies
3
Views
1K
Replies
1
Views
2K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
3
Views
1K
Top