1
$\begingroup$

I am currently working on CLRS 1.13. The idea is to use Stirling's approximation to prove that

$${2n \choose n} = \frac{2^{2n}}{\sqrt{\pi n}} \left( 1 + O \left( \frac{1}{n} \right) \right)$$

Now directly replacing Stirling's approximation I arrive to something like:

$${2n \choose n} = \frac{2^{2n} \left( 1 + \Theta(\frac{1}{2n}) \right)}{ \sqrt{\pi n} \left(1 + \Theta( \frac{1}{n}) \right)^2 }$$

Now the quotient is a function that ends up being $O(\frac{1}{n})$ because we have terms in $O(\frac{1}{n})$ and $O(\frac{1}{2n})$. The problem is that even if there is a quotient of two functions that are $O(\frac{1}{n})$.

I don't know if the result is still $O(\frac{1}{n})$. In fact I haven't seen any general rule for the quotient of two big $O$ s.

Is there a general rule that I can apply here?

$\endgroup$
2
$\begingroup$

Just simply use the inequality $1 + \Theta(1/n) \geq 1$ in the denominator. You will get the required answer.

$\endgroup$
5
  • $\begingroup$ @plop $f(n)$ is positive right? so the inequality should be correct for all $f \in \Theta(1/n)$. $\endgroup$ – Inuyasha Yagami Feb 1 at 16:59
  • $\begingroup$ I was wrong. I was reading $\Theta$ and thinking $O$. For $n$ large, the elements of $\Theta$ do become positive. $\endgroup$ – plop Feb 1 at 17:02
  • $\begingroup$ @plop I am not aware of the definition of $\Omega$ or $O$ for negative functions. :p $\endgroup$ – Inuyasha Yagami Feb 1 at 18:09
  • $\begingroup$ @plop However, in Stirling's approximation, the function $f$ is indeed positive. $\endgroup$ – Inuyasha Yagami Feb 1 at 18:10
  • 1
    $\begingroup$ It is the same definitions. They don't make any assumption about the sign of the function. In the case of $\Theta(1/n)$ it follows as a consequence of the definition, since $f\in\Theta(1/n)$ must satisfy $K_1/n\leq f(n)\leq K_2/n$ for some $K_1,K_2>0$ and sufficiently large $n$. $\endgroup$ – plop Feb 1 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.