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.
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.
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 log(n!) \in \Theta (n log(n)). 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...
Again, that's what I'm trying to prove. If I could prove this, the original theorem would be trivial for me.
I really do appreciate the help, of course! Thanks for pointing me in the right direction.
Oops. I didn't mean to imply that it's already true, but instead that it is what I still have to show. I see where you are coming from now.
2a n^2 + 4b n \geq 4|b|n + 4bn \geq 0 is true if 2a n^2 \geq 4|b|n. This would be true assuming that n \geq 2|b| / a . On the other hand:
an^2 + 4c \geq...
That's exactly what the "informal" use of theta notation shows. I totally understand (and believe) the informal justification, but I'm having trouble with showing it formally.
Thanks for your response! I'll take a closer look at it when I get out of work =P
The problem states that a > 0, but there are no restrictions on the other two coefficients.
Hey everybody,
I'm a little embarrassed to be asking this question as I feel it is extremely easy, but I will do so anyway. I'm self studying some algorithms, and the book that I'm using claims that
a n^2 + b n + c \in \Omega(n^2)
Of course, this is equivalent to saying that there...